Premium
Supereulerian complementary graphs
Author(s) -
Lai HongJian
Publication year - 1993
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190170214
Subject(s) - combinatorics , mathematics , eulerian path , graph , bound graph , simple graph , discrete mathematics , graph power , line graph , lagrangian , mathematical physics
Nebeský in [12] show that for any simple graph with n ≥ 5 vertices, either G or G c contains an eulerian subgraph with order at least n ‐ 1, with an explicitly described class of exceptional graphs. In this note, we show that if G is a simple graph with n ≥ 61 vertices, then either G or G c is supereulerian, with some exceptions. We also characterize all these exceptional cases. These results are applied to show that if G is a simple graph with n ≥ 61 vertices such that both G and G c are connected, then either G or G c has a 4‐flow, or both G and G c have cut‐edges. © 1993 John Wiley & Sons, Inc.