Three-regular subgraphs of four-regular graphs
It is known that any simple 4-regular graph contains a 3-regular subgraph. In the present paper the authors consider finite undirected graphs with multiple edges but without loops. They extend the above given result to such 4-regular graphs \(G\). They use the concept of Euler orientation defined as follows: Let \(G= (V,E)\) be a 4-regular graph with \(v_i\in V\), \(| V|= n\), \(| E|= 2n\). Then an Euler orientation of \(G\) is a partition \(E= \bigcup^n_{i= 1} A_{v_i}\) of the set \(E\) of edges such that \(A_{v_i}\) and \(A_{v_j}\) are disjoint for any \(i\neq j\) and each \(A_{v_i}\) has exactly two edges both incident with \(v_i\). \(N= N(G)\) denote the number of Euler orientations of \(G\). The main result of the paper is Theorem 2.2: A 4-regular graph \(G\) with \(n\) vertices has a 3-regular subgraph if \(N\not\equiv 1\pmod 3\). This theorem is extended to Theorem 2.3: A \(2m\)-regular graph \(G\) has a \(p\)-regular subgraph (\(p\) a prime such that \(p- 1\leq m\)) if \(N\not\equiv 1\pmod p\). Further a set of 4-regular graphs with multiple edges is given which have no 3-regular subgraphs but for which the authors know exactly the number \(N\) of Euler orientations. Finally a conjecture of Thomassen is reduced to 4-regular graphs only with multiple edges. It asserts that any 4-regular connected graph with an even number of vertices has a 3-regular subgraph. This has been proved by the second author.
- Largest 2-regular subgraphs in 3-regular graphs
- On 3-regular 4-ordered graphs
- Construction of 4-Regular Graphs
- scientific article; zbMATH DE number 3902701 (Why is no real title available?)
- scientific article; zbMATH DE number 691480 (Why is no real title available?)
- scientific article; zbMATH DE number 930115 (Why is no real title available?)
- scientific article; zbMATH DE number 1456823 (Why is no real title available?)
- 3-Regular subgraphs and (3,1)-colorings of 4-regular pseudographs
- Subeulerian oriented graphs
- Three-regular parts of four-regular graphs
This page was built for publication: Three-regular subgraphs of four-regular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5906272)
