Three-regular subgraphs of four-regular graphs (Q5906272): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Heinz Joachim Presia / rank | |||
Property / reviewed by | |||
Property / reviewed by: Heinz Joachim Presia / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/eujc.1997.0150 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2043546239 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 02:07, 20 March 2024
scientific article; zbMATH DE number 1199957
Language | Label | Description | Also known as |
---|---|---|---|
English | Three-regular subgraphs of four-regular graphs |
scientific article; zbMATH DE number 1199957 |
Statements
Three-regular subgraphs of four-regular graphs (English)
0 references
27 October 1998
0 references
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.
0 references
Euler orientation
0 references
partition
0 references
conjecture of Thomassen
0 references