𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Spanning subgraphs of graphs partitioned into two isomorphic pieces

✍ Scribed by Anthony Bonato

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
124 KB
Volume
51
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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

📜 SIMILAR VOLUMES

Partitioning a graph into two isomorphic
Partitioning a graph into two isomorphic pieces
✍ Anthony Bonato; Richard Nowakowski 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB

## Abstract A simple graph __G__ has the neighbour‐closed‐co‐neighbour property, or ncc property, if for all vertices __x__ of __G__, the subgraph induced by the set of neighbours of __x__ is isomorphic to the subgraph induced by the set of non‐neighbours of __x__. We present characterizations of g

Sharp bounds for decompositions of graph
Sharp bounds for decompositions of graphs into completer-partite subgraphs
✍ Gregory, David A.; Vander Meulen, Kevin N. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 435 KB 👁 2 views

If G is a graph on n vertices and r 2 2, w e let m,(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, f(G). In determining m,(G), w e may assume that no two vertices of G have the same neighbor set. For such reduced graphs G, w