Premium
Some sufficient conditions for the existence of a 1‐factor
Author(s) -
Nebeský Ladislav
Publication year - 1978
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.3190020308
Subject(s) - mathematics , combinatorics , lemma (botany) , induced subgraph isomorphism problem , induced subgraph , graph , graph factorization , order (exchange) , discrete mathematics , graph power , line graph , voltage graph , vertex (graph theory) , ecology , poaceae , finance , economics , biology
Abstract The following theorem is proved: Let G be a graph of even order. Assume that there exists a connected spanning subgraph F of G such that for every set U of four vertices in G , if the subgraph of F induced by U is a star, then the subgraph of G induced by U is complete. Then G has a 1‐factor. The above theorem is derived from another sufficient condition for the existence of a 1‐factor, which is also proved in this paper (Lemma 1).