Premium
Spanning subgraphs of graphs partitioned into two isomorphic pieces
Author(s) -
Bonato Anthony
Publication year - 2006
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.20123
Subject(s) - combinatorics , mathematics , countable set , cograph , induced subgraph , discrete mathematics , induced subgraph isomorphism problem , graph , line graph , pathwidth , voltage graph , vertex (graph theory)
A graph has the neighbor‐closed‐co‐neighbor, or ncc property, if for each of its vertices x , the subgraph induced by the neighbor set of x is isomorphic to the subgraph induced by the closed non‐neighbor set of x . As proved by Bonato and Nowakowski [5], graphs with the ncc property are characterized by the existence of perfect matchings satisfying certain local conditions. In the present article, we investigate the spanning subgraphs of ncc graphs, which we name sub‐ncc. Several equivalent characterizations of finite sub‐ncc graphs are given, along with a polynomial time algorithm for their recognition. The infinite sub‐ncc graphs are characterized, and we demonstrate the existence of a countable universal sub‐ncc graph satisfying a strong symmetry condition called pseudo‐homogeneity. © 2005 Wiley Periodicals, Inc. J Graph Theory