|
|||||
|
|
Degree sequence and supereulerian graphs |
|
| Authors: | Suohai Fan Yehong Shao Ju Zhou |
| Institution: | a Department of Mathematics, Jinan University Guangzhou 510632, PR China b Department of Mathematics, West Virginia University, Morgantown, WV 26506, United States c Arts and Science, Ohio University Southern, Ironton, OH 45638, United States d Department of Mathematics, Penn State Worthington Scranton, Dunmore, PA 18512, United States |
| Abstract: | A sequence d=(d1,d2,…,dn) 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=(d1,d2,…,dn) has a supereulerian realization if and only if dn≥2 and that d is line-hamiltonian if and only if either d1=n−1, or ∑di=1di≤∑dj≥2(dj−2). |
| Keywords: | Degree sequence Collapsible graphs Hamiltonian line graphs Supereulerian graphs |
| 本文献已被 ScienceDirect 等数据库收录！ | |