✦ LIBER ✦

On some conjectures on cubic 3-connected graphs

✍ Scribed by Jean-Luc Fouquet; Henri Thuillier

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 969 KB
Volume: 80
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90294-r

No coin nor oath required. For personal study only.

✦ Synopsis

Our purpose is to consider the following conjectures:

Conjecture 1 (Barneffe). . Every cubic 3-connected bipartite planar graph is Hamiltonian. Conjecture 2 (Jaeger). Every cubic cyclically 4-edge connected graph G has a cycle C such that G -V(C) is acyclic. Conjecture 3 (Jackson, Fleischner). Every cubic cyclically 4-edge connected graph G has a cycle C such that V(G) -V(C) is an independent set of vertices.

We show that the previous conjectures are respectively equivalent to the following conjectures:

Conjecture 1'. For every pair of edges belonging to the boundary of one given face of a cubic 3-connected bipartite planar graph, there exists a Hamiltonian cycle through these edges. Conjecture 2'. For every pair of non-adjacent edges of a cyclically 4-edge connected cubic graph G there exists a cycle C through these edges such that G -V(C) is acyclic. Conjecture 3'. For every pair of non-adjacent edges of a cyclically 4-edge connected cubic graph G there exists a cycle C through these edges such that V(G) -V(C) is an independent set of vertices.

Preliminary results

1.1. Definitions and known results

Terminology not defined here is that of [l]. All graphs considered here are finite and without loops. We will use the fact that if G is a graph of maximum degree at most three then the connectivity of G (denoted by K(G)) is equal to its edge-connectivity (denoted by A(G)). A cubic graph is a simple 3-regular graph. Let F be a nonempty subset of E(G). The subgraph of G whose vertex set is the set of vertices incident to edges in F and whose edge set is F is denoted by (F). The cocycle of a proper induced subgraph H of a graph G is the edge cut [V(H), I'(G) -V(H)1 consisting of the edges with one end in V(H) and the other in V(G) -V(H). F or a graph G having at least two vertex-disjoint cycles, a 0012-365X/90/$3.50

📜 SIMILAR VOLUMES

On the Number of Cycles in 3-Connected C

On the Number of Cycles in 3-Connected Cubic Graphs

✍ R.E.L Aldred; Carsten Thomassen 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 228 KB

Let f (n) be the minimum number of cycles present in a 3-connected cubic graph on n vertices. In 1986, C. A. Barefoot, L. Clark, and R. Entringer (Congr. Numer. 53, 1986) showed that f (n) is subexponential and conjectured that f (n) is superpolynomial. We verify this by showing that, for n sufficie

Some remarks on domination in cubic grap

Some remarks on domination in cubic graphs

✍ Bohdan Zelinka 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 445 KB

We study three recently introduced numerical invariants of graphs, namely, the signed domination number y., the minus domination number 7 and the majority domination number ymaj. An upper bound for ys and lower bounds for ;'-and Y,,~ are found, in terms of the order of the graph.

On locating cubic subgraphs in bounded-d

On locating cubic subgraphs in bounded-degree connected bipartite graphs

✍ Iain A Stewart 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 236 KB

We show that the problem of deciding whether a connected bipartite graph of degree at most 4 has a cubic subgraph is NP-complete.

Harary's conjectures on integral sum gra

Harary's conjectures on integral sum graphs

✍ Zhibo Chen 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 167 KB

On n-connected graphs

✍ Branko Grünbaum 📂 Article 📅 1969 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB

The main aim of the present note is the proof of a variant of the MENGER-WHITNEY theorem on n-connected graphs (Theorem 1 below). While the result itself is well known (being, for example, a special case of the theorem of MENGER mentioned in Remark I), two of its aspects deserve attention. First, it

On hamiltonian-connected graphs

✍ Ronald J. Gould; Xingxing Yu 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 735 KB

## Abstract One of the most fundamental results concerning paths in graphs is due to Ore: In a graph __G__, if deg __x__ + deg __y__ ≧ |__V__(__G__)| + 1 for all pairs of nonadjacent vertices __x, y__ ≅ __V__(__G__), then __G__ is hamiltonian‐connected. We generalize this result using set degrees.