In this paper the problem of the existence of regular nut graphs is addressed. A generalization of Fowler’s Construction which is a local enlargement applied to a vertex in a graph is introduced to ...generate nut graphs of higher order. Let N(ρ) denote the set of integers n such that there exists a regular nut graph of degree ρ and order n. It is proven that N(3) = {12} ∪ {2k : k ≥ 9} and that N(4) = {8, 10, 12} ∪ {n : n ≥ 14}. The problem of determining N(ρ) for ρ > 4 remains completely open.
A nut graph is a singular graph with one-dimensional kernel and corresponding eigenvector with no zero elements. The problem of determining the orders
for which
-regular nut graphs exist was recently ...posed by Gauci, Pisanski and Sciriha. These orders are known for
4. Here we solve the problem for all remaining cases
11 and determine the complete lists of all
-regular nut graphs of order
for small values of
and
. The existence or non-existence of small regular nut graphs is determined by a computer search. The main tool is a construction that produces, for any
-regular nut graph of order
, another
-regular nut graph of order
+2
. If we are given a sufficient number of
-regular nut graphs of consecutive orders, called seed graphs, this construction may be applied in such a way that the existence of all
-regular nut graphs of higher orders is established. For even
the orders
are indeed consecutive, while for odd
the orders
are consecutive even numbers. Furthermore, necessary conditions for combinations of order and degree for vertex-transitive nut graphs are derived.
In this paper we are interested in the fine-grained complexity of determining whether there is an homomorphism from an input graph G to a fixed graph H (the H-coloring problem). The starting point is ...the observation that these problems can be formulated in the language of CSPs, and that (partial) polymorphisms of binary relations are of paramount importance in the study of complexity classes of such CSPs. Thus, we first investigate the expressivity of binary symmetric relations E_{H} and their corresponding (partial) polymorphisms \text{pPol}(E_{H}) . For irreflexive graphs we observe that there is no pair of graphs H and H^{\prime} such that \text{pPol}(E_{H})\subseteq \text{pPol}(E_{H^{\prime}}) , unless E_{H^{\prime}}=\emptyset or H =H^{\prime} . More generally we show the existence of an n -ary relation R whose partial polymorphisms strictly subsume those of H and such that \text{CSP} (R) is \mathcal{NP} complete if and only if H contains an odd cycle of length at most n . Motivated by this we also describe the sets of total polymorphisms of every nontrivial clique, every odd cycle, as well as certain cores. We finish the paper with some noteworthy questions for future research.
Increasingly there is a need to process graphs that are larger than the available memory on today’s machines. Many systems have been developed with graph representations that are efficient and ...compact for out-of-core processing. A necessary task in these systems is memory management. This paper presents a system called Cacheap which automatically and efficiently manages the available memory to maximize the speed of graph processing, minimize the amount of disk access, and maximize the utilization of memory for graph data. It has a simple interface that can be easily adopted by existing graph engines. The paper describes the new system, uses it in recent graph engines, and demonstrates its integer factor improvements in the speed of large-scale graph processing.
A retract of a graph Γ is an induced subgraph Ψ of Γ such that there exists a homomorphism from Γ to Ψ whose restriction to Ψ is the identity map. A graph is a core if it has no nontrivial retracts. ...In general, the minimal retracts of a graph are cores and are unique up to isomorphism; they are called the core of the graph. A graph Γ is G‐symmetric if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set and also transitive on the set of ordered pairs of adjacent vertices. If in addition the vertex set of Γ admits a nontrivial partition that is preserved by G, then Γ is an imprimitive G‐symmetric graph. In this paper cores of imprimitive symmetric graphs Γ of order a product of two distinct primes are studied. In many cases the core of Γ is determined completely. In other cases it is proved that either Γ is a core or its core is isomorphic to one of two graphs, and conditions on when each of these possibilities occurs is given.
Graphs with a common eigenvalue deck Sciriha, Irene
Linear algebra and its applications,
2009, 2009-01-00, Letnik:
430, Številka:
1
Journal Article
Recenzirano
Odprti dostop
In this paper, we consider graphs whose deck consists of cards (which are the vertex-deleted subgraphs) that share the same eigenvalue, say
μ
. We show that, the characteristic polynomial can be ...reconstructed from the deck, providing a new proof of Tutte’s result for this class of graphs. Moreover, for the subclass of non-singular graphs, the graph can be uniquely reconstructed from the eigenvectors of the cards associated with the eigenvalue
μ
. The remaining graphs in this class are shown to be
μ
-cores graphs.
This study proposes a fault-tolerant technique on application mapping and spare core allocation in networks-on-chip. The proposed technique sets the place of spare cores among free non-faulty ...processing cores, dynamically. Here, dynamically setting means that the places of spare cores are tuned for each application and are not fixed in the platform statically. Some vertices of each application core graph can be known as critical, based on their vulnerabilities, the performance degradation and the energy consumption overheads because of negative impacts of failure recovery. This technique locates the spare cores near to the critical cores. As the main theoretical contribution, the problem of spare core placement and its impression on system fault-tolerance properties is discussed. Some metrics are investigated to be considered in spare core allocation. The results of 1 000 000 fault injection experiments show that the proposed technique leads to communication energy reductions and performance improvement, compared with related works.
This article proposes a reconfigurable Network-on-Chip (NoC) architecture based on mesh topology. It provides a local reconfiguration of cores to connect to any of the neighboring routers, depending ...upon the currently executing application. The area overhead for this local reconfiguration has been shown to be very small. We have also presented the strategy to map the cores of an application set onto this architecture. This has been achieved via a two-phase procedure. In the first phase, the cores of the combined application set are mapped tentatively to individual routers, minimizing the communication cost. In the second phase, for each application, positions of individual cores are finalized. A core gets attached to any neighbor of its tentative allocation. We have proposed Integer Linear Programming (ILP) formulation of both the phases. Since ILP takes large amount of CPU time, we have also formulated a Particle Swarm Optimization (PSO)-based solution for the two phases. A heuristic approach has also been developed for the reconfiguration. Comparison of communication cost, latency and network energy have been carried out for the applications, before and after reconfiguration. It shows significant improvement in performance via reconfiguration.
PDF
