共查询到20条相似文献,搜索用时 15 毫秒
1.
Several isomorphism classes of graph coverings of a graph G have been enumerated by many authors (see [3], [8]–[15]). A covering of G is called circulant if its covering graph is circulant. Recently, the authors [4] enumerated the isomorphism classes of circulant
double coverings of a certain kind, called typical, and showed that no double covering of a circulant graph of valency 3 is
circulant. In this paper, the isomorphism classes of connected circulant double coverings of a circulant graph of valency
4 are enumerated. As a consequence, it is shown that no double covering of a non-circulant graph G of valency 4 can be circulant if G is vertex-transitive or G has a prime power of vertices.
The first author is supported by NSF of China (No. 60473019) and by NKBRPC (2004CB318000), and the second author is supported
by Com2MaC-KOSEF (R11-1999-054) in Korea. 相似文献
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.
We present a formula to enumerate non-isomorphic circulant digraphs of order n with connection sets of cardinality 2. This formula simplifies to C(n,2)=3×2a−1−4 in the case when n=2a(a≥3), and when n=pa(where p is an odd prime and a≥1). The number of non-isomorphic directed double networks are also enumerated. 相似文献
4.
Hiranmoy Pal 《Discrete Mathematics》2018,341(4):889-895
The transition matrix of a graph corresponding to the adjacency matrix is defined by where . The graph is said to exhibit pretty good state transfer between a pair of vertices and if there exists a sequence of real numbers such that , where is a complex number of unit modulus. We present a class of circulant graphs admitting pretty good state transfer. Also we find some circulant graphs not exhibiting pretty good state transfer. This generalizes several pre-existing results on circulant graphs admitting pretty good state transfer. 相似文献
5.
Riadh Khennoufa 《Discrete Mathematics》2008,308(24):6316-6329
In this paper, the total chromatic number and the fractional total chromatic number of circulant graphs are studied. For cubic circulant graphs we give upper bounds on the fractional total chromatic number and for 4-regular circulant graphs we find the total chromatic number for some cases and we give the exact value of the fractional total chromatic number in most cases. 相似文献
6.
Seiya Negami 《Advances in Mathematics》2010,225(4):1717-1738
Let G be a connected graph. We reformulate Stark and Terras' Galois Theory for a quotient H of a regular covering K of a graph G by using voltage assignments. As applications, we show that the weighted Bartholdi L-function of H associated to the representation of the covering transformation group of H is equal to that of G associated to its induced representation in the covering transformation group of K. Furthermore, we express the weighted Bartholdi zeta function of H as a product of weighted Bartholdi L-functions of G associated to irreducible representations of the covering transformation group of K. We generalize Stark and Terras' Galois Theory to digraphs, and apply to weighted Bartholdi L-functions of digraphs. 相似文献
7.
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. 相似文献
8.
The spectrum of a digraph in general contains real and complex eigenvalues. A digraph is called a Gaussian integral digraph if it has a Gaussian integral spectrum that is all eigenvalues are Gaussian integers. In this paper, we consider Gaussian integral digraphs among circulant digraphs. 相似文献
9.
Edward Dobson 《Discrete Mathematics》2008,308(24):6047-6055
C.H. Li recently made the following conjecture: Let Γ be a circulant digraph of order n=n1n2 and degree m, where gcd(n1,n2)=1, n1 divides 4k, where k is odd and square-free, and every prime divisor of n2 is greater than m, or, if Γ is a circulant graph, every prime divisor of n2 is greater than 2m. Then Γ is a CI-digraph of Zn. In this paper we verify that this conjecture is true. 相似文献
10.
11.
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. 相似文献
12.
A graph theoretical analog of Brauer-Siegel theory for zeta functions of number fields is developed using the theory of Artin L-functions for Galois coverings of graphs from parts I and II. In the process, we discuss possible versions of the Riemann hypothesis for the Ihara zeta function of an irregular graph. 相似文献
13.
14.
Robert R. Lewis 《Discrete Mathematics》2018,341(9):2553-2566
This paper considers the degree-diameter problem for undirected circulant graphs. For degrees 10 and 11, newly discovered families of circulant graphs of arbitrary diameter are presented which are largest known and are conjectured to be extremal. They are also the largest-known Abelian Cayley graphs of these degrees. For each such family, the order of every graph in the family is defined by a quintic polynomial function of the diameter which is specific to the family. The elements of the generating set for each graph are similarly defined by a set of polynomials in the diameter. The existence of the graphs in the degree 10 families has been proved for all diameters. These graphs are consistent with a conjecture on the order of extremal Abelian Cayley and circulant graphs of any degree and diameter. 相似文献
15.
Eyal Loz 《Discrete Mathematics》2009,309(10):3125-3130
We derive an upper bound on the number of vertices in regular graphs of given degree and diameter arising as regular coverings of dipoles over abelian groups. 相似文献
16.
Jesper Makholm Byskov 《Operations Research Letters》2004,32(6):547-556
We give tight upper bounds on the number of maximal independent sets of size k (and at least k and at most k) in graphs with n vertices. As an application of the proof, we construct improved algorithms for graph colouring and computing the chromatic number of a graph. 相似文献
17.
Iwao Sato 《Discrete Mathematics》2008,308(12):2600-2606
We define the weighted Bartholdi zeta function and a weighted L-function of a graph G, and give determinant expressions of them. Furthermore, we present a decomposition formula for the weighted Bartholdi zeta function of a regular covering of G by weighted L-functions of G. 相似文献
18.
Seungsang Oh 《Discrete Mathematics》2017,340(12):2762-2768
An independent vertex set of a graph is a set of vertices of the graph in which no two vertices are adjacent, and a maximal independent set is one that is not a proper subset of any other independent set. In this paper we count the number of maximal independent sets of vertices on a complete rectangular grid graph. More precisely, we provide a recursive matrix-relation producing the partition function with respect to the number of vertices. The asymptotic behavior of the maximal hard square entropy constant is also provided. We adapt the state matrix recursion algorithm, recently invented by the author to answer various two-dimensional regular lattice model problems in enumerative combinatorics and statistical mechanics. 相似文献
19.
Let be the circulant graph with . We study the reduced Euler characteristic of the independence complex for with prime and for with odd prime, proving that in both cases does not vanish. We also give an example of circulant graph whose independence complex has
which equals 0, giving a negative answer to R. Hoshino. 相似文献
20.
Cheryl Praeger 《Discrete Mathematics》2009,309(10):3006-127
In this paper we determine the positive integers n and k for which there exists a homogeneous factorisation of a complete digraph on n vertices with k ‘common circulant’ factors. This means a partition of the arc set of the complete digraph Kn into k circulant factor digraphs, such that a cyclic group of order n acts regularly on the vertices of each factor digraph whilst preserving the edges, and in addition, an overgroup of this permutes the factor digraphs transitively amongst themselves. This determination generalises a previous result for self-complementary circulants. 相似文献