共查询到20条相似文献,搜索用时 15 毫秒
1.
A graph is well-covered if every independent set can be extended to a maximum independent set. We show that it is co-NP-complete to determine whether an arbitrary graph is well-covered, even when restricted to the family of circulant graphs. Despite the intractability of characterizing the complete set of well-covered circulant graphs, we apply the theory of independence polynomials to show that several families of circulants are indeed well-covered. Since the lexicographic product of two well-covered circulants is also a well-covered circulant, our partial characterization theorems enable us to generate infinitely many families of well-covered circulants previously unknown in the literature. 相似文献
2.
Integral circulant graphs 总被引:2,自引:0,他引:2
Wasin So 《Discrete Mathematics》2006,306(1):153-158
In this note we characterize integral graphs among circulant graphs. It is conjectured that there are exactly 2τ(n)-1 non-isomorphic integral circulant graphs on n vertices, where τ(n) is the number of divisors of n. 相似文献
3.
4.
A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7. 相似文献
5.
6.
The diameter of a graph measures the maximal distance between any pair of vertices. The diameters of many small-world networks, as well as a variety of other random graph models, grow logarithmically in the number of nodes. In contrast, the worst connected networks are cycles whose diameters increase linearly in the number of nodes. In the present study we consider an intermediate class of examples: Cayley graphs of cyclic groups, also known as circulant graphs or multi-loop networks. We show that the diameter of a random circulant 2k-regular graph with n vertices scales as n 1/k , and establish a limit theorem for the distribution of their diameters. We obtain analogous results for the distribution of the average distance and higher moments. 相似文献
7.
8.
9.
We investigate the conjecture that every circulant graph X admits a k‐isofactorization for every k dividing |E(X)|. We obtain partial results with an emphasis on small values of k. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 406–414, 2006 相似文献
10.
Elizabeth C.M. Maritz 《Quaestiones Mathematicae》2018,41(1):49-63
Let Π = {S1, S2, . . . , Sk} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex v ∈ V (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S1), d(v, S2), . . . , d(v, Sk)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, v ∈ V (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(Cn(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators. 相似文献
11.
Let S? {1, …, n?1} satisfy ?S = S mod n. The circulant graph G(n, S) with vertex set {v0, v1,…, vn?1} and edge set E satisfies vivj?E if and only if j ? i ∈ S, where all arithmetic is done mod n. The circulant digraph G(n, S) is defined similarly without the restriction S = ? S. Ádám conjectured that if and only if S = uS′ for some unit u mod n. In this paper we prove the conjecture true if n = pq where p and q are distinct primes. We also show that it is not generally true when n = p2, and determine exact conditions on S that it be true in this case. We then show as a simple consequence that the conjecture is false in most cases when n is divisible by p2 where p is an odd prime, or n is divisible by 24. 相似文献
12.
Andrea Semani?ová 《Discrete Mathematics》2006,306(18):2263-2269
A graph is called magic (supermagic) if it admits a labelling of the edges by pairwise different (and consecutive) integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In the paper, we characterize magic circulant graphs and 3-regular supermagic circulant graphs. We establish some conditions for supermagic circulant graphs. 相似文献
13.
14.
Igor Shparlinski 《Linear algebra and its applications》2006,414(1):378-382
We give an explicit construction of circulant graphs of very high energy. This construction is based on Gauss sums. We also show the Littlewood conjecture can be used to establish new result for a certain class of circulant graphs. 相似文献
15.
《Journal of Graph Theory》2018,88(3):434-448
The natural infinite analog of a (finite) Hamilton cycle is a two‐way‐infinite Hamilton path (connected spanning 2‐valent subgraph). Although it is known that every connected 2k‐valent infinite circulant graph has a two‐way‐infinite Hamilton path, there exist many such graphs that do not have a decomposition into k edge‐disjoint two‐way‐infinite Hamilton paths. This contrasts with the finite case where it is conjectured that every 2k‐valent connected circulant graph has a decomposition into k edge‐disjoint Hamilton cycles. We settle the problem of decomposing 2k‐valent infinite circulant graphs into k edge‐disjoint two‐way‐infinite Hamilton paths for , in many cases when , and in many other cases including where the connection set is or . 相似文献
16.
Javier Barajas 《Discrete Mathematics》2009,309(18):5687-5696
Given a set D of a cyclic group C, we study the chromatic number of the circulant graph G(C,D) whose vertex set is C, and there is an edge ij whenever i−j∈D∪−D. For a fixed set D={a,b,c:a<b<c} of positive integers, we compute the chromatic number of circulant graphs G(ZN,D) for all N≥4bc. We also show that, if there is a total order of D such that the greatest common divisors of the initial segments form a decreasing sequence, then the chromatic number of G(Z,D) is at most 4. In particular, the chromatic number of a circulant graph on ZN with respect to a minimum generating set D is at most 4. The results are based on the study of the so-called regular chromatic number, an easier parameter to compute. The paper also surveys known results on the chromatic number of circulant graphs. 相似文献
17.
Path connected graphs 总被引:5,自引:0,他引:5
18.
19.
Jozef Jirsek 《Journal of Graph Theory》2005,49(1):59-68
Locke and Witte described infinite families of nonhamiltonian circulant oriented graphs. We show that for infinitely many of them the reversal of any arc produces a hamiltonian cycle. This solves an open problem stated by Thomassen in 1987. We also use these graphs to construct counterexamples to Ádám's conjecture on arc reversal. One of them is a counterexample with the smallest known number of vertices. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 59–68, 2005 相似文献
20.
The existence of perfect state transfer in quantum spin networks based on integral circulant graphs has been considered recently by Saxena, Severini and Shparlinski. We give the simple condition for characterizing integral circulant graphs allowing the perfect state transfer in terms of its eigenvalues. Using that, we complete the proof of results stated by Saxena, Severini and Shparlinski. Moreover, it is shown that in the class of unitary Cayley graphs there are only two of them allowing perfect state transfer. 相似文献