𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Partitioning a graph into two isomorphic pieces

✍ Scribed by Anthony Bonato; Richard Nowakowski

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
137 KB
Volume
44
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 graphs with the ncc property via the existence of certain perfect matchings, and thereby prove that the ncc graphs can be recognized in polynomial time. Operations preserving the ncc property are discussed, and the graphs with the ncc property that are r‐regular, where r ≤ 5, are classified. The graphs with the ncc property that are locally H, for certain graphs H are classified. Infinite graphs with the ncc property are discussed. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 1–14, 2003

📜 SIMILAR VOLUMES

Spanning subgraphs of graphs partitioned
Spanning subgraphs of graphs partitioned into two isomorphic pieces
✍ Anthony Bonato 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB

## 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 p

Packing two forests into a bipartite gra
Packing two forests into a bipartite graph
✍ Wang, Hong 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 292 KB 👁 3 views

For two integers a and b, we say that a bipartite graph G admits an ( a , b)-bipartition if G has a bipartition ( X , Y ) such that /XI = a and ( Y / = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit ( a , b)-bipartitions. In this note, w

Cutting a graph into two dissimilar halv
Cutting a graph into two dissimilar halves
✍ Paul Erdós; Mark Goldberg; János Pach; Joel Spencer 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 357 KB

Given a graph G and a subset S of the vertex set of G, the discrepancy of S is defined as the difference between the actual and expected numbers of the edges in the subgraph induced on S. We show that for every graph with n vertices and e edges, n < e < n ( n -1)/4, there is an n/2-element subset wi

Packing two bipartite graphs into a comp
Packing two bipartite graphs into a complete bipartite graph
✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 3 views

For two integers a and b, we say that a bipartite graph G admits an (a, b)bipartition if G has a bipartition (X, Y ) such that |X| = a and |Y | = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit (a, b)-bipartitions. In this paper, we prove

Partitions of a graph into paths with pr
Partitions of a graph into paths with prescribed endvertices and lengths
✍ Hikoe Enomoto; Katsuhiro Ota 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB 👁 3 views

For a graph G, let ' 2 (G ) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| n i 1 k a i and ' 2 (G ) ! n k À 1, then for any k vertices v 1 , v 2 , F F F , v k in G, there exist vertex-disjoint paths P 1 , P 2 , F F F , P k such that |V (P i )| a i and v

Packing two copies of a sparse graph int
Packing two copies of a sparse graph into a graph with restrained maximum degree
✍ Hong Wang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB

## Abstract We show that if a tree __T__ is not a star, then there is an embedding σ of __T__ in the complement of __T__ such that the maximum degree of __T__∪σ(__T__) is at most Δ(__T__)+2. We also show that if __G__ is a graph of order __n__ with __n__−1 edges, then with several exceptions, there