The spanning subgraphs of eulerian graphs

F. T. Boesch, Charles Suffel, R. Tindell

Research output: Contribution to journalArticle

56 Citations (Scopus)

Abstract

It is shown that a connected graph G spans an eulerian graph if and only if G is not spanned by an odd complete bigraph K(2m + 1, 2n + 1). A disconnected graph spans an eulerian graph if and only if it is not the union of the trivial graph with a complete graph of odd order. Exact formulas are obtained for the number of lines which must be added to such graphs in order to get eulerian graphs.

Original languageEnglish (US)
Pages (from-to)79-84
Number of pages6
JournalJournal of Graph Theory
Volume1
Issue number1
DOIs
StatePublished - Jan 1 1977

Fingerprint

Eulerian Graph
Spanning Subgraph
Graph in graph theory
Odd
If and only if
Complete Graph
Connected graph
Trivial
Union
Line

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Cite this

Boesch, F. T. ; Suffel, Charles ; Tindell, R. / The spanning subgraphs of eulerian graphs. In: Journal of Graph Theory. 1977 ; Vol. 1, No. 1. pp. 79-84.
@article{feaddb2f26c84df28ea28326fa72c34c,
title = "The spanning subgraphs of eulerian graphs",
abstract = "It is shown that a connected graph G spans an eulerian graph if and only if G is not spanned by an odd complete bigraph K(2m + 1, 2n + 1). A disconnected graph spans an eulerian graph if and only if it is not the union of the trivial graph with a complete graph of odd order. Exact formulas are obtained for the number of lines which must be added to such graphs in order to get eulerian graphs.",
author = "Boesch, {F. T.} and Charles Suffel and R. Tindell",
year = "1977",
month = "1",
day = "1",
doi = "https://doi.org/10.1002/jgt.3190010115",
language = "English (US)",
volume = "1",
pages = "79--84",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "1",

}

The spanning subgraphs of eulerian graphs. / Boesch, F. T.; Suffel, Charles; Tindell, R.

In: Journal of Graph Theory, Vol. 1, No. 1, 01.01.1977, p. 79-84.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The spanning subgraphs of eulerian graphs

AU - Boesch, F. T.

AU - Suffel, Charles

AU - Tindell, R.

PY - 1977/1/1

Y1 - 1977/1/1

N2 - It is shown that a connected graph G spans an eulerian graph if and only if G is not spanned by an odd complete bigraph K(2m + 1, 2n + 1). A disconnected graph spans an eulerian graph if and only if it is not the union of the trivial graph with a complete graph of odd order. Exact formulas are obtained for the number of lines which must be added to such graphs in order to get eulerian graphs.

AB - It is shown that a connected graph G spans an eulerian graph if and only if G is not spanned by an odd complete bigraph K(2m + 1, 2n + 1). A disconnected graph spans an eulerian graph if and only if it is not the union of the trivial graph with a complete graph of odd order. Exact formulas are obtained for the number of lines which must be added to such graphs in order to get eulerian graphs.

UR - http://www.scopus.com/inward/record.url?scp=85014231964&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85014231964&partnerID=8YFLogxK

U2 - https://doi.org/10.1002/jgt.3190010115

DO - https://doi.org/10.1002/jgt.3190010115

M3 - Article

VL - 1

SP - 79

EP - 84

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 1

ER -