𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Three-regular subgraphs of four-regular graphs

✍ Scribed by V. Chvátal; H. Fleischner; J. Sheehan; C. Thomassen

Publisher
John Wiley and Sons
Year
1979
Tongue
English
Weight
553 KB
Volume
3
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Berge conjectured that every finite simple 4‐regular graph G contains a 3‐regular subgraph. We prove that this conjecture is true if the cyclic edge connectivity λ^c^(G) of G is at least 10. Also we prove that if G is a smallest counterexample, then λ^c^(G) is either 6 or 8.

📜 SIMILAR VOLUMES

Three-regular Subgraphs of Four-regular
Three-regular Subgraphs of Four-regular Graphs
✍ O. Moreno; V.A. Zinoviev 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 85 KB

For any 4-regular graph G (possibly with multiple edges), we prove that, if the number N of distinct Euler orientations of G is such that N ≡ 1 (mod 3), then G has a 3-regular subgraph. It gives the new 4-regular graphs with multiple edges which have no 3-regular subgraphs, for which we know the num

Regular factors in vertex-deleted subgra
Regular factors in vertex-deleted subgraphs of regular graphs
✍ P. Katerinis 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 258 KB

Let G be a 2r-regular, 2r-edge-connected graph of odd order and m be an integer such that 1 2rw(W)+2ec(S',S')-2 c d,-&)+2rlS'I. ES' (12) But CxsS' ## dc-o(x)=&sS dG-D(x)+dc-&)=CXEs dG,-D(x)+e&,S)+dG-&). Thus (12) implies, ## 2rIDI>2ro(W)+2eG(S',S')-2 c dc,-o(x)+e,(u,S)+d,-,(u) +WS'I. XC.7

Distance-regular Subgraphs in a Distance
Distance-regular Subgraphs in a Distance-regular Graph, III
✍ Akira Hiraki 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 254 KB

Let ⌫ be a distance-regular graph with l (1 , a 1 , b 1 ) ϭ 1 and c s ϩ 1 ϭ 1 for some positive integer s . We show the existence of a certain distance-regular graph of diameter s , containing given two vertices at distance s , as a subgraph in ⌫ .

Distance-regular Subgraphs in a Distance
Distance-regular Subgraphs in a Distance-regular Graph, IV
✍ Akira Hiraki 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 280 KB

Let ⌫ be a distance-regular graph with a 1 Ͼ 0 , r ϭ max ͕ j 3 ( c j , a j , b j ) ϭ ( c 1 , a 1 , b 1 ) ͖ у 2 and a i ϭ a 1 c i , for 1 р i р 2 r . Take any u and in ⌫ at distance r ϩ 1 . We show that there exists a collinearity graph of a generalized 2( r ϩ 1)-gon of order ( a 1 ϩ 1 , c r ϩ 1 Ϫ 1)