Skip to main navigation Skip to search Skip to main content

Supereulerian graphs and the Petersen graph, II

    Research output: Contribution to journalArticlepeer-review

    Abstract

    In this note, we verify two conjectures of Catlin in [J. Graph Theory 13 (1989) 465 - 483] for graphs with at most 11 vertices. These are used to prove the following theorem which improves prior results in [10] and [13]:

    Let G be a 3-edge-connected simple graph with order n. If n is large and if for every edge 11.v E E(G), d(u) + d(v) 2 % - 2, then either G has a spanning eulerian subgraph or G can be contracted to the Petersen graph.

    Original languageAmerican English
    JournalScholarship and Professional Work - LAS
    Volume48
    StatePublished - Mar 1 1995

    Disciplines

    • Computer Sciences
    • Mathematics

    Cite this