zbMATH — the first resource for mathematics

Degree sequence and supereulerian graphs. (English) Zbl 1165.05005
Summary: A sequence \(d=(d_{1},d_{2},\ldots ,d_n)\) is graphic if there is a simple graph \(G\) with degree sequence \(d\), and such a graph \(G\) is called a realization of \(d\). A graphic sequence \(d\) is line-hamiltonian if \(d\) has a realization \(G\) such that \(L(G)\) is hamiltonian, and is supereulerian if \(d\) has a realization \(G\) with a spanning eulerian subgraph. In this paper, it is proved that a nonincreasing graphic sequence \(d=(d_{1},d_{2},\ldots ,d_n)\) has a supereulerian realization if and only if \(d_n\geq 2\) and that \(d\) is line-hamiltonian if and only if either \(d_{1}=n - 1\), or \(\sum _{d_i=1}d_i\leq \sum _{d_j\geq 2}(d_j - 2)\).

05C07 Vertex degrees
05C45 Eulerian and Hamiltonian graphs
Full Text: DOI
[1] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), American Elsevier New York · Zbl 1134.05001
[2] Catlin, P.A., A reduction method to find spanning Eulerian subgraphs, J. graph theory, 12, 29-45, (1988) · Zbl 0659.05073
[3] Edmonds, J., Existence of \(k\)-edge connected ordinary graphs with prescribed degree, J. res. nat. bur. stand., ser. B, 68, 7374, (1964)
[4] Hakimi, S.L., On the realizability of a set of integers as degrees of the vertices of a graph, SIAM J. appl. math., 10, 496-506, (1962) · Zbl 0109.16501
[5] Harary, F.; Nash-Williams, C.St.J.A., On eulerian and Hamiltonian graphs and line graphs, Canad. math. bull., 8, 701-709, (1965) · Zbl 0136.44704
[6] Havel, V., A remark on the existence of finite graphs (Czech.), Časopis Pěst. mat., 80, 477-480, (1955) · Zbl 0068.37202
[7] F. Jaeger, On interval hypergraphs and nowhere-zero flow in graphs, Research Report of Mathematics Application and Information, Universite Scientifique et Medicale et Institut National Polytechnique de Grenoble, No. 126, Juillet, 1978
[8] Kleitman, D.J.; Wang, D.L., Algorithm for constructing graphs and digraphs with given valences and factors, Discrete math., 6, 7988, (1973) · Zbl 0263.05122
[9] Luo, R.; Zang, W.A.; Zhang, C.-Q., Nowhere-zero 4-flows, simultaneous edge-colorings, and critical partial Latin squares, Combinatorica, 24, 4, 641-657, (2004) · Zbl 1070.05042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.