Degree sequence and supereulerian graphs

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

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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 = 1 di ≤ ∑dj ≥ 2 (dj - 2).

Original languageEnglish (US)
Pages (from-to)6626-6631
Number of pages6
JournalDiscrete Mathematics
Volume308
Issue number24
DOIs
StatePublished - Dec 28 2008

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Degree sequence and supereulerian graphs'. Together they form a unique fingerprint.

Cite this