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)
Journal	Journal of Graph Theory
DOIs	https://doi.org/10.1002/jgt.23027
State	Accepted/In press - 2023

Keywords

acyclic graph
deck
graph reconstruction
tree

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Online availability

10.1002/jgt.23027

Cite this

@article{08137af032544539a5e20c59669b0a9f,

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 = "Publisher Copyright: {\textcopyright} 2023 Wiley Periodicals LLC.",

year = "2023",

doi = "10.1002/jgt.23027",

language = "English (US)",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

}

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

PY - 2023

Y1 - 2023

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=85168443672&partnerID=8YFLogxK

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

U2 - 10.1002/jgt.23027

DO - 10.1002/jgt.23027

M3 - Article

AN - SCOPUS:85168443672

SN - 0364-9024

JO - Journal of Graph Theory

JF - Journal of Graph Theory

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Related links

Fingerprint

Cite this