共查询到20条相似文献，搜索用时 15 毫秒
1.
M. N. Ellingham Emily A. Marshall Kenta Ozeki Shoichi Tsuchiya 《Journal of Graph Theory》2019,90(4):459-483
Tutte showed that -connected planar graphs are Hamiltonian, but it is well known that -connected planar graphs need not be Hamiltonian. We show that -minor-free -connected planar graphs are Hamiltonian. This does not extend to -minor-free -connected graphs in general, as shown by the Petersen graph, and does not extend to -minor-free -connected planar graphs, as we show by an infinite family of examples. 相似文献
2.
Perry Iverson 《Journal of Graph Theory》2016,82(3):253-264
Projective planar graphs can be characterized by a set of 35 excluded minors. However, these 35 are not equally important. A set of 3‐connected members of is excludable if there are only finitely many 3‐connected nonprojective planar graphs that do not contain any graph in as a minor. In this article, we show that there are precisely two minimal excludable sets, which have sizes 19 and 20, respectively. 相似文献
3.
4.
Every planar graph is known to be acyclically 7‐choosable and is conjectured to be acyclically 5‐choosable (O. V. Borodin, D. G. Fon‐Der‐Flaass, A. V. Kostochka, E. Sopena, J Graph Theory 40 (2002), 83–90). This conjecture if proved would imply both Borodin's (Discrete Math 25 (1979), 211–236) acyclic 5‐color theorem and Thomassen's (J Combin Theory Ser B 62 (1994), 180–181) 5‐choosability theorem. However, as yet it has been verified only for several restricted classes of graphs. Some sufficient conditions are also obtained for a planar graph to be acyclically 4‐ and 3‐choosable. In particular, the acyclic 4‐choosability was proved for the following planar graphs: without 3‐, 4‐, and 5‐cycles (M. Montassier, P. Ochem, and A. Raspaud, J Graph Theory 51 (2006), 281–300), without 4‐, 5‐, and 6‐cycles, or without 4‐, 5‐, and 7‐cycles, or without 4‐, 5‐, and intersecting 3‐cycles (M. Montassier, A. Raspaud, W. Wang, Topics Discrete Math (2006), 473–491), and neither 4‐ and 5‐cycles nor 8‐cycles having a triangular chord (M. Chen and A. Raspaud, Discrete Math. 310(15–16) (2010), 2113–2118). The purpose of this paper is to strengthen these results by proving that each planar graph without 4‐ and 5‐cycles is acyclically 4‐choosable. 相似文献
5.
We prove that any circulant graph of order n with connection set S such that n and the order of ?(S), the subgroup of ? that fixes S set‐wise, are relatively prime, is also a Cayley graph on some noncyclic group, and shows that the converse does not hold in general. In the special case of normal circulants whose order is not divisible by 4, we classify all such graphs that are also Cayley graphs of a noncyclic group, and show that the noncyclic group must be metacyclic, generated by two cyclic groups whose orders are relatively prime. We construct an infinite family of normal circulants whose order is divisible by 4 that are also normal Cayley graphs on dihedral and noncyclic abelian groups. © 2005 Wiley Periodicals, Inc. J Graph Theory 相似文献
6.
The notion of a symmetric Hamiltonian cycle system (HCS) of a graph Γ has been introduced and studied by J. Akiyama, M. Kobayashi, and G. Nakamura [J Combin Des 12 (2004), 39–45] for , by R. A. Brualdi and M. W. Schroeder [J Combin Des 19 (2011), 1–15] for , and then naturally extended by V. Chitra and A. Muthusamy [Discussiones Mathematicae Graph Theory, to appear] to the multigraphs and . In each case, there must be an involutory permutation ψ of the vertices fixing all the cycles of the HCS and at most one vertex. Furthermore, for , this ψ should be precisely the permutation switching all pairs of endpoints of the edges of I. An HCS is cyclic if it is invariant under some cyclic permutation of all the vertices. The existence question for a cyclic HCS of has been completely solved by Jordon and Morris [Discrete Math (2008), 2440–2449]—and we note that their cyclic construction is also symmetric for (mod 8). It is then natural to study the existence problem of an HCS of a graph or multigraph Γ as above which is both cyclic and symmetric. In this paper, we completely solve this problem: in the case of even order, the final answer is that cyclicity and symmetry can always cohabit when a cyclic solution exists. On the other hand, imposing that a cyclic HCS of odd order is also symmetric is very restrictive; we prove in fact that an HCS of with both properties exists if and only if is a prime. 相似文献
7.
Mark Ginn 《Journal of Graph Theory》1999,30(2):71-76
We show that the minimum set of unordered graphs that must be forbidden to get the same graph class characterized by forbidding a single ordered graph is infinite. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 71–76, 1999 相似文献
8.
Shung‐Liang Wu 《组合设计杂志》2012,20(1):23-39
In this article, it is proved that for each even integer m?4 and each admissible value n with n>2m, there exists a cyclic m‐cycle system of Kn, which almost resolves the existence problem for cyclic m‐cycle systems of Kn with m even. © 2011 Wiley Periodicals, Inc. J Combin Designs 20:23–39, 2012 相似文献
9.
In this paper, we study the existence problem for cyclic ‐cycle decompositions of the graph , the complete multipartite graph with parts of size , and give necessary and sufficient conditions for their existence in the case that . 相似文献
10.
A circulant is a Cayley graph of a cyclic group. Arc-transitive circulants of square-free order are classified. It is shown that an arc-transitive circulant of square-free order n is one of the following: the lexicographic product
, or the deleted lexicographic
, where n = bm and is an arc-transitive circulant, or is a normal circulant, that is, Aut has a normal regular cyclic subgroup. 相似文献
11.
Let H be a given graph. A graph G is said to be H‐free if G contains no induced copies of H. For a class of graphs, the graph G is ‐free if G is H‐free for every . Bedrossian characterized all the pairs of connected subgraphs such that every 2‐connected ‐free graph is hamiltonian. Faudree and Gould extended Bedrossian's result by proving the necessity part of the result based on infinite families of non‐hamiltonian graphs. In this article, we characterize all pairs of (not necessarily connected) graphs such that there exists an integer n0 such that every 2‐connected ‐free graph of order at least n0 is hamiltonian. 相似文献
12.
轮网络是由Cayley图模型设计出来的一种新型互连网络模型.星网络、冒泡排序网络、修正冒泡排序网络可嵌入轮网络.为了揭示它的整体结构,对轮网络提出如下一簇猜想:轮网络是边不交的i个Hamilton圈及2(n-i)-2个完美匹配的并,其中1≤i≤(n-1);并证明了当n=4,5,6,1≤i≤3时,猜想成立. 相似文献
13.
14.
Andrea Vietri 《组合设计杂志》2004,12(4):299-310
We exhibit cyclic (Kv, Ck)‐designs with v > k, v ≡ k (mod 2k), for k an odd prime power but not a prime, and for k = 15. Such values were the only ones not to be analyzed yet, under the hypothesis v ≡ k (mod 2k). Our construction avails of Rosa sequences and approximates the Hamiltonian case (v = k), which is known to admit no cyclic design with the same values of k. As a particular consequence, we settle the existence question for cyclic (Kv, Ck)‐designs with k a prime power. © 2004 Wiley Periodicals, Inc. J Combin Designs 12: 299–310, 2004. 相似文献
15.
A graph H is strongly immersed in G if H is obtained from G by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of H are mapped to distinct vertices of G (branch vertices) and edges of H are mapped to pairwise edge‐disjoint paths in G, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices. We describe the structure of graphs avoiding a fixed graph as a strong immersion. The theorem roughly states that a graph which excludes a fixed graph as a strong immersion has a tree‐like decomposition into pieces glued together on small edge cuts such that each piece of the decomposition has a path‐like linear decomposition isolating the high degree vertices. 相似文献
16.
Reinhard Diestel 《Journal of Graph Theory》2000,35(4):273-277
We prove the following recent conjecture of Halin. Let Γ0 be the class of all graphs, and for every ordinal μ > 0 let Γμ be the class of all graphs containing infinitely many disjoint connected graphs from Γλ, for every λ < μ. Then a graph lies in all these classes Γμ if and only if it contains a subdivision of the infinite binary tree. Published by John Wiley & Sons, Inc., 2000 J Graph Theory 35: 273–277, 2000 相似文献
17.
Yaming Yu 《Journal of Graph Theory》2004,47(4):317-321
A graph is Y Δ Y reducible if it can be reduced to a single vertex by a sequence of series‐parallel reductions and Y Δ Y transformations. The class of Y Δ Y reducible graphs is minor closed. We found a large number of minor minimal Y Δ Y irreducible graphs: a family of 57578 31‐edge graphs and another 40‐edge graph. It is still an open problem to characterize Y Δ Y reducible graphs in terms of a finite set of forbidden minors. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 317–321, 2004 相似文献
18.
Valery Liskovets 《Journal of Algebraic Combinatorics》2003,18(3):189-209
We establish analytically several new identities connecting enumerators of different types of circulant graphs mainly of prime, twice prime and prime-squared orders. In particular, it is shown that the half-sum of the number of undirected circulants and the number of undirected self-complementary circulants of prime order is equal to the number of directed self-complementary circulants of the same order. Several identities hold only for prime orders p such that (p + 1)/2 is also prime. Some conjectured generalizations and interpretations are discussed. 相似文献
19.
The necessary and sufficient conditions for the existence of a 1‐rotational k‐cycle system of the complete graph Kv are established. The proof provides an algorithm able to determine, directly and explicitly, an odd k‐cycle system of Kv whenever such a system exists. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 283–293, 2009 相似文献
20.
All graphs are finite simple undirected and of no isolated vertices in this paper. Using the theory of coset graphs and permutation groups, it is completed that a classification of locally transitive graphs admitting a non-Abelian group with cyclic Sylow subgroups. They are either the union of the family of arc-transitive graphs, or the union of the family of bipartite edge-transitive graphs. 相似文献