Jean-Luc Fouquet, Jean-Marie Vanherpe (2010)
Discussiones Mathematicae Graph Theory
Similarity:
A conjecture of Mácajová and Skoviera asserts that every bridgeless cubic graph has two perfect matchings whose intersection does not contain any odd edge cut. We prove this conjecture for graphs with few vertices and we give a stronger result for traceable graphs.
Jochen Harant (2013)
Discussiones Mathematicae Graph Theory
Similarity:
Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.
Jean-Luc Fouquet, Jean-Marie Vanherpe (2011)
Discussiones Mathematicae Graph Theory
Similarity:
If G is a bridgeless cubic graph, Fulkerson conjectured that we can find 6 perfect matchings (a Fulkerson covering) with the property that every edge of G is contained in exactly two of them. A consequence of the Fulkerson conjecture would be that every bridgeless cubic graph has 3 perfect matchings with empty intersection (this problem is known as the Fan Raspaud Conjecture). A FR-triple is a set of 3 such perfect matchings. We show here how to derive a Fulkerson covering from two FR-triples....
T. McKee (1988)
Fundamenta Mathematicae
Similarity:
Stodolsky, B.Y. (2008)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Xiumei Wang, Yixun Lin (2018)
Discussiones Mathematicae Graph Theory
Similarity:
For a 2-connected cubic graph G, the perfect matching polytope P(G) of G contains a special point [...] xc=(13,13,…,13) . The core index ϕ(P(G)) of the polytope P(G) is the minimum number of vertices of P(G) whose convex hull contains xc. The Fulkerson’s conjecture asserts that every 2-connected cubic graph G has six perfect matchings such that each edge appears in exactly two of them, namely, there are six vertices of P(G) such that xc is the convex combination of them, which implies...
Bill Jackson, Carol A. Whitehead (1999)
Annales de l'institut Fourier
Similarity:
François Jaeger conjectured in 1974 that every cyclically 4-connected cubic graph is dual hamiltonian, that is to say the vertices of can be partitioned into two subsets such that each subset induces a tree in . We shall make several remarks on this conjecture.
Bert Hartnell, Douglas F. Rall (1995)
Discussiones Mathematicae Graph Theory
Similarity:
The domination number of a graph G is the smallest order, γ(G), of a dominating set for G. A conjecture of V. G. Vizing [5] states that for every pair of graphs G and H, γ(G☐H) ≥ γ(G)γ(H), where G☐H denotes the Cartesian product of G and H. We show that if the vertex set of G can be partitioned in a certain way then the above inequality holds for every graph H. The class of graphs G which have this type of partitioning includes those whose 2-packing number is no smaller than γ(G)-1 as...
Pouria Salehi Nowbandegani, Hossein Esfandiari, Mohammad Hassan Shirdareh Haghighi, Khodakhast Bibak (2014)
Discussiones Mathematicae Graph Theory
Similarity:
The Erdős-Gyárfás conjecture states that every graph with minimum degree at least three has a cycle whose length is a power of 2. Since this conjecture has proven to be far from reach, Hobbs asked if the Erdős-Gyárfás conjecture holds in claw-free graphs. In this paper, we obtain some results on this question, in particular for cubic claw-free graphs
Bostjan Bresar (2001)
Discussiones Mathematicae Graph Theory
Similarity:
A dominating set D for a graph G is a subset of V(G) such that any vertex in V(G)-D has a neighbor in D, and a domination number γ(G) is the size of a minimum dominating set for G. For the Cartesian product G ⃞ H Vizing's conjecture [10] states that γ(G ⃞ H) ≥ γ(G)γ(H) for every pair of graphs G,H. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when γ(G) = γ(H) = 3.
Julien Bensmail (2017)
Discussiones Mathematicae Graph Theory
Similarity:
In the context of a conjecture of Erdős and Gyárfás, we consider, for any q ≥ 2, the existence of q-power cycles (i.e., with length a power of q) in cubic graphs. We exhibit constructions showing that, for every q ≥ 3, there exist arbitrarily large cubic graphs with no q-power cycles. Concerning the remaining case q = 2 (which corresponds to the conjecture of Erdős and Gyárfás), we show that there exist arbitrarily large cubic graphs whose all 2-power cycles have length 4 only, or 8...
M. Kano, Changwoo Lee, Kazuhiro Suzuki (2008)
Discussiones Mathematicae Graph Theory
Similarity:
For a set S of connected graphs, a spanning subgraph F of a graph is called an S-factor if every component of F is isomorphic to a member of S. It was recently shown that every 2-connected cubic graph has a {Cₙ | n ≥ 4}-factor and a {Pₙ | n ≥ 6}-factor, where Cₙ and Pₙ denote the cycle and the path of order n, respectively (Kawarabayashi et al., J. Graph Theory, Vol. 39 (2002) 188-193). In this paper, we show that every connected cubic bipartite graph has a {Cₙ | n ≥ 6}-factor, and has...
Chartrand, Gary, Saba, Farrokh, Cooper, John K.jun., Harary, Frank, Wall, Curtiss E. (1982)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Michael D. Plummer, Michael Stiebitz, Bjarne Toft (2003)
Discussiones Mathematicae Graph Theory
Similarity:
Hadwiger's Conjecture seems difficult to attack, even in the very special case of graphs G of independence number α(G) = 2. We present some results in this special case.
Oum, Sang-Il (2011)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Terasoma Terasoma (1990)
Mathematische Annalen
Similarity:
Jerzy A. Filar, Michael Haythorpe, Giang T. Nguyen (2010)
Discussiones Mathematicae Graph Theory
Similarity:
Almost all d-regular graphs are Hamiltonian, for d ≥ 3 [8]. In this note we conjecture that in a similar, yet somewhat different, sense almost all cubic non-Hamiltonian graphs are bridge graphs, and present supporting empirical results for this prevalence of the latter among all connected cubic non-Hamiltonian graphs.
József Balogh, John Lenz, Hehui Wu (2011)
Discussiones Mathematicae Graph Theory
Similarity:
The Hadwiger number h(G) of a graph G is the maximum size of a complete minor of G. Hadwiger's Conjecture states that h(G) ≥ χ(G). Since χ(G) α(G) ≥ |V(G)|, Hadwiger's Conjecture implies that α(G) h(G) ≥ |V(G)|. We show that (2α(G) - ⌈log_{τ}(τα(G)/2)⌉) h(G) ≥ |V(G)| where τ ≍ 6.83. For graphs with α(G) ≥ 14, this improves on a recent result of Kawarabayashi and Song who showed (2α(G) - 2) h(G) ≥ |V(G) | when α(G) ≥ 3.