Forbidden subgraphs for supereulerian and hamiltonian graphs

Xiaojing Yang, Junfeng Du, Liming Xiong*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

A graph is called supereulerian if it has a spanning eulerian subgraph. A graph is said to be hamiltonian if it has a spanning cycle. A nontrivial path is called a branch if it has only internal vertices of degree two and end vertices of degree not two. Let S be a set of branches of G, then S is called a branch cut if G−S has more components than G. A minimal branch cut is called a branch-bond. In this paper, we characterize one or pairs of those forbidden subgraphs that force a 2-edge-connected graph satisfying that every odd branch-bond has an edge branch to be supereulerian. We also characterize one or pairs of those forbidden subgraphs that force a 2-connected supereulerian graph to be hamiltonian.

Original languageEnglish
Pages (from-to)192-200
Number of pages9
JournalDiscrete Applied Mathematics
Volume288
DOIs
Publication statusPublished - 15 Jan 2021

Keywords

  • Branch
  • Even factor
  • Forbidden subgraph
  • Hamiltonian
  • Supereulerian

Fingerprint

Dive into the research topics of 'Forbidden subgraphs for supereulerian and hamiltonian graphs'. Together they form a unique fingerprint.

Cite this