Degree sequence and supereulerian graphs. (English) Zbl 1165.05005

Fan, Suohai; Lai, Hong-Jian; Shao, Yehong; Zhang, Taoye; Zhou, Ju

Discrete Math. 308, No. 24, 6626-6631 (2008).

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)\).

MSC:

05C07	Vertex degrees
05C45	Eulerian and Hamiltonian graphs

Keywords:

degree sequence; collapsible graphs; Hamiltonian line graphs; supereulerian graphs

References:

[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