Families of pairs of graphs with a large number of common cards Export

@article{citeulike:6083215, abstract = {The vertex-deleted subgraph G-v, obtained from the graph G by deleting the vertex v and all edges incident to v, is called a card of G. The deck of G is the multiset of its unlabelled vertex-deleted subgraphs. The number of common cards of G and H (or between G and H) is the cardinality of the multiset intersection of the decks of G and H. In this article, we present infinite families of pairs of graphs of order n ge 4 that have at least common cards; we conjecture that these, along with a small number of other families constructed from them, are the only pairs of graphs having this many common cards, for sufficiently large n. This leads us to propose a new stronger version of the Reconstruction Conjecture. In addition, we present an infinite family of pairs of graphs with the same degree sequence that have common cards, for appropriate values of n, from which we can construct pairs having slightly fewer common cards for all other values of nge10. We also present infinite families of pairs of forests and pairs of trees with and common cards, respectively. We then present new families that have the maximum number of common cards when one graph is connected and the other disconnected. Finally, we present a family with a large number of common cards, where one graph is a tree and the other unicyclic, and discuss how many cards are required to determine whether a graph is a tree. {\copyright} 2009 Wiley Periodicals, Inc. J Graph Theory}, address = {School of Economics, Mathematics and Statistics, Birkbeck College University of London, United Kingdom; School of Computer Science and Information Systems, Birkbeck College, University of London, United Kingdom}, author = {Bowler, Andrew and Brown, Paul and Fenner, Trevor}, citeulike-article-id = {6083215}, citeulike-linkout-0 = {http://dx.doi.org/10.1002/jgt.20415}, citeulike-linkout-1 = {http://www3.interscience.wiley.com/cgi-bin/abstract/122364229/ABSTRACT}, doi = {10.1002/jgt.20415}, issn = {1097-0118}, journal = {Journal of Graph Theory}, keywords = {graphs, reconstruction}, number = {9999}, pages = {n/a+}, posted-at = {2009-11-07 18:29:23}, priority = {2}, title = {Families of pairs of graphs with a large number of common cards}, url = {http://dx.doi.org/10.1002/jgt.20415}, volume = {9999}, year = {2009} }

TY - JOUR ID - citeulike:6083215 L3 - citeulike-article-id:6083215 N2 - The vertex-deleted subgraph G-v, obtained from the graph G by deleting the vertex v and all edges incident to v, is called a card of G. The deck of G is the multiset of its unlabelled vertex-deleted subgraphs. The number of common cards of G and H (or between G and H) is the cardinality of the multiset intersection of the decks of G and H. In this article, we present infinite families of pairs of graphs of order n ge 4 that have at least common cards; we conjecture that these, along with a small number of other families constructed from them, are the only pairs of graphs having this many common cards, for sufficiently large n. This leads us to propose a new stronger version of the Reconstruction Conjecture. In addition, we present an infinite family of pairs of graphs with the same degree sequence that have common cards, for appropriate values of n, from which we can construct pairs having slightly fewer common cards for all other values of nge10. We also present infinite families of pairs of forests and pairs of trees with and common cards, respectively. We then present new families that have the maximum number of common cards when one graph is connected and the other disconnected. Finally, we present a family with a large number of common cards, where one graph is a tree and the other unicyclic, and discuss how many cards are required to determine whether a graph is a tree. © 2009 Wiley Periodicals, Inc. J Graph Theory IS - 9999 JF - Journal of Graph Theory SN - 1097-0118 AD - School of Economics, Mathematics and Statistics, Birkbeck College University of London, United Kingdom; School of Computer Science and Information Systems, Birkbeck College, University of London, United Kingdom TI - Families of pairs of graphs with a large number of common cards VL - 9999 SP - n/a KW - graphs KW - reconstruction AU - Bowler, Andrew AU - Brown, Paul AU - Fenner, Trevor PY - 2009/// UR - http://dx.doi.org/10.1002/jgt.20415 ER -