Premium
Recognizing connectedness from vertex‐deleted subgraphs
Author(s) -
Bowler Andrew,
Brown Paul,
Fenner Trevor,
Myrvold Wendy
Publication year - 2011
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.20531
Subject(s) - combinatorics , mathematics , social connectedness , vertex (graph theory) , disjoint sets , graph , induced subgraph , discrete mathematics , upper and lower bounds , psychology , psychotherapist , mathematical analysis
Let G be a graph of order n . The vertex‐deleted subgraph G − v , obtained from G by deleting the vertex v and all edges incident to v , is called a card of G . Let H be another graph of order n , disjoint from G . Then the number of common cards of G and H is the maximum number of disjoint pairs ( v, w ), where v and w are vertices of G and H , respectively, such that G − v ≅ H − w . We prove that if G is connected and H is disconnected, then the number of common cards of G and H is at most ⌊ n /2⌋ + 1. Thus, we can recognize the connectedness of a graph from any ⌊ n /2⌋ + 2 of its cards. Moreover, we completely characterize those pairs of graphs that attain the upper bound and show that, with the exception of six pairs of graphs of order at most 7, any pair of graphs that attains the maximum is in one of four infinite families. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:285‐299, 2011