Acyclic graphs with at least 2ℓ + 1 vertices are ℓ-recognizable

Alexandr V. Kostochka; Mina Nahvi; Douglas B. West; Dara Zirlin

doi:10.1002/jgt.23027

Acyclic graphs with at least 2ℓ + 1 vertices are ℓ-recognizable

Alexandr V. Kostochka, Mina Nahvi, Douglas B. West, Dara Zirlin

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

The (Formula presented.) -deck of an (Formula presented.) -vertex graph is the multiset of subgraphs obtained from it by deleting (Formula presented.) vertices. A family of (Formula presented.) -vertex graphs is (Formula presented.) -recognizable if every graph having the same (Formula presented.) -deck as a graph in the family is also in the family. We prove that the family of (Formula presented.) -vertex graphs with no cycles is (Formula presented.) -recognizable when (Formula presented.) (except for (Formula presented.)). As a consequence, the family of (Formula presented.) -vertex trees is (Formula presented.) -recognizable when (Formula presented.) and (Formula presented.). It is known that this fails when (Formula presented.).

Original language	English (US)
Pages (from-to)	184-200
Number of pages	17
Journal	Journal of Graph Theory
Volume	109
Issue number	2
Early online date	Aug 22 2023
DOIs	https://doi.org/10.1002/jgt.23027
State	Published - Jun 2025

Keywords

acyclic graph
deck
graph reconstruction
tree

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Online availability

10.1002/jgt.23027

Library availability

Discover UIUC Full Text

Cite this

@article{5bfbf085cced4148ba62c22adb53f937,

title = "Acyclic graphs with at least 2ℓ + 1 vertices are ℓ-recognizable",

abstract = "The (Formula presented.) -deck of an (Formula presented.) -vertex graph is the multiset of subgraphs obtained from it by deleting (Formula presented.) vertices. A family of (Formula presented.) -vertex graphs is (Formula presented.) -recognizable if every graph having the same (Formula presented.) -deck as a graph in the family is also in the family. We prove that the family of (Formula presented.) -vertex graphs with no cycles is (Formula presented.) -recognizable when (Formula presented.) (except for (Formula presented.)). As a consequence, the family of (Formula presented.) -vertex trees is (Formula presented.) -recognizable when (Formula presented.) and (Formula presented.). It is known that this fails when (Formula presented.).",

keywords = "acyclic graph, deck, graph reconstruction, tree",

author = "Kostochka, {Alexandr V.} and Mina Nahvi and West, {Douglas B.} and Dara Zirlin",

note = "We thank the referees for their careful reading and many helpful comments. Alexandr V. Kostochka was supported by NSF grants DMS\u20101600592 and DMS\u20102153507. Douglas B. West was supported by National Natural Science Foundation of China grants NSFC 11871439, 11971439, and U20A2068. Dara Zirlin was supported by Arnold O. Beckman Campus Research Board Award RB20003 of the University of Illinois and by NSF RTG grant DMS\u20101937241. We thank the referees for their careful reading and many helpful comments. Alexandr V. Kostochka was supported by NSF grants DMS-1600592 and DMS-2153507. Douglas B. West was supported by National Natural Science Foundation of China grants NSFC 11871439, 11971439, and U20A2068. Dara Zirlin was supported by Arnold O. Beckman Campus Research Board Award RB20003 of the University of Illinois and by NSF RTG grant DMS-1937241.",

year = "2025",

month = jun,

doi = "10.1002/jgt.23027",

language = "English (US)",

volume = "109",

pages = "184--200",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "2",

}

TY - JOUR

T1 - Acyclic graphs with at least 2ℓ + 1 vertices are ℓ-recognizable

AU - Kostochka, Alexandr V.

AU - Nahvi, Mina

AU - West, Douglas B.

AU - Zirlin, Dara

N1 - We thank the referees for their careful reading and many helpful comments. Alexandr V. Kostochka was supported by NSF grants DMS\u20101600592 and DMS\u20102153507. Douglas B. West was supported by National Natural Science Foundation of China grants NSFC 11871439, 11971439, and U20A2068. Dara Zirlin was supported by Arnold O. Beckman Campus Research Board Award RB20003 of the University of Illinois and by NSF RTG grant DMS\u20101937241. We thank the referees for their careful reading and many helpful comments. Alexandr V. Kostochka was supported by NSF grants DMS-1600592 and DMS-2153507. Douglas B. West was supported by National Natural Science Foundation of China grants NSFC 11871439, 11971439, and U20A2068. Dara Zirlin was supported by Arnold O. Beckman Campus Research Board Award RB20003 of the University of Illinois and by NSF RTG grant DMS-1937241.

PY - 2025/6

Y1 - 2025/6

N2 - The (Formula presented.) -deck of an (Formula presented.) -vertex graph is the multiset of subgraphs obtained from it by deleting (Formula presented.) vertices. A family of (Formula presented.) -vertex graphs is (Formula presented.) -recognizable if every graph having the same (Formula presented.) -deck as a graph in the family is also in the family. We prove that the family of (Formula presented.) -vertex graphs with no cycles is (Formula presented.) -recognizable when (Formula presented.) (except for (Formula presented.)). As a consequence, the family of (Formula presented.) -vertex trees is (Formula presented.) -recognizable when (Formula presented.) and (Formula presented.). It is known that this fails when (Formula presented.).

AB - The (Formula presented.) -deck of an (Formula presented.) -vertex graph is the multiset of subgraphs obtained from it by deleting (Formula presented.) vertices. A family of (Formula presented.) -vertex graphs is (Formula presented.) -recognizable if every graph having the same (Formula presented.) -deck as a graph in the family is also in the family. We prove that the family of (Formula presented.) -vertex graphs with no cycles is (Formula presented.) -recognizable when (Formula presented.) (except for (Formula presented.)). As a consequence, the family of (Formula presented.) -vertex trees is (Formula presented.) -recognizable when (Formula presented.) and (Formula presented.). It is known that this fails when (Formula presented.).

KW - acyclic graph

KW - deck

KW - graph reconstruction

KW - tree

UR - http://www.scopus.com/inward/record.url?scp=105002977690&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=105002977690&partnerID=8YFLogxK

U2 - 10.1002/jgt.23027

DO - 10.1002/jgt.23027

M3 - Article

AN - SCOPUS:105002977690

SN - 0364-9024

VL - 109

SP - 184

EP - 200

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 2

ER -

Acyclic graphs with at least 2ℓ + 1 vertices are ℓ-recognizable

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this