Edge-apexing in hereditary classes of graphs Article Swipe

PDF

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2403.09456

A class $\mathcal{G}$ of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by $G^{epex}$ the class of graphs that are at most one edge away from being in $\mathcal{G}$. We note that $G^{epex}$ is hereditary and prove that if a hereditary class $\mathcal{G}$ has finitely many forbidden induced subgraphs, then so does $G^{epex}$. The hereditary class of cographs consists of all graphs $G$ that can be generated from $K_1$ using complementation and disjoint union. Cographs are precisely the graphs that do not have the $4$-vertex path as an induced subgraph. For the class of edge-apex cographs our main result bounds the order of such forbidden induced subgraphs by 8 and finds all of them by computer search.

Related Topics

Enhanced Data Rates For Gsm Evolution

Combinatorics

Mathematics

Computer Science

Artificial Intelligence

Concepts

Enhanced Data Rates for GSM Evolution Combinatorics Mathematics Computer science Artificial intelligence

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2403.09456
PDF: https://arxiv.org/pdf/2403.09456
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4392873863

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4392873863

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2403.09456

Digital Object Identifier
Title: Edge-apexing in hereditary classes of graphs

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-03-14

Full publication date if available
Authors: Jagdeep Singh, Vaidy Sivaraman

List of authors in order
Landing page: https://arxiv.org/abs/2403.09456

Publisher landing page
PDF URL: https://arxiv.org/pdf/2403.09456

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2403.09456

Direct OA link when available
Concepts: Enhanced Data Rates for GSM Evolution, Combinatorics, Mathematics, Computer science, Artificial intelligence

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4392873863
doi	https://doi.org/10.48550/arxiv.2403.09456
ids.doi	https://doi.org/10.48550/arxiv.2403.09456
ids.openalex	https://openalex.org/W4392873863
fwci
type	preprint
title	Edge-apexing in hereditary classes of graphs
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10374
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9987000226974487
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Advanced Graph Theory Research
topics[1].id	https://openalex.org/T12541
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9958000183105469
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1703
topics[1].subfield.display_name	Computational Theory and Mathematics
topics[1].display_name	Graph Labeling and Dimension Problems
topics[2].id	https://openalex.org/T11476
topics[2].field.id	https://openalex.org/fields/26
topics[2].field.display_name	Mathematics
topics[2].score	0.9882000088691711
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/2608
topics[2].subfield.display_name	Geometry and Topology
topics[2].display_name	Graph theory and applications
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C162307627
concepts[0].level	2
concepts[0].score	0.607472836971283
concepts[0].wikidata	https://www.wikidata.org/wiki/Q204833
concepts[0].display_name	Enhanced Data Rates for GSM Evolution
concepts[1].id	https://openalex.org/C114614502
concepts[1].level	1
concepts[1].score	0.489062637090683
concepts[1].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[1].display_name	Combinatorics
concepts[2].id	https://openalex.org/C33923547
concepts[2].level	0
concepts[2].score	0.3911944627761841
concepts[2].wikidata	https://www.wikidata.org/wiki/Q395
concepts[2].display_name	Mathematics
concepts[3].id	https://openalex.org/C41008148
concepts[3].level	0
concepts[3].score	0.3168795704841614
concepts[3].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[3].display_name	Computer science
concepts[4].id	https://openalex.org/C154945302
concepts[4].level	1
concepts[4].score	0.2393786907196045
concepts[4].wikidata	https://www.wikidata.org/wiki/Q11660
concepts[4].display_name	Artificial intelligence
keywords[0].id	https://openalex.org/keywords/enhanced-data-rates-for-gsm-evolution
keywords[0].score	0.607472836971283
keywords[0].display_name	Enhanced Data Rates for GSM Evolution
keywords[1].id	https://openalex.org/keywords/combinatorics
keywords[1].score	0.489062637090683
keywords[1].display_name	Combinatorics
keywords[2].id	https://openalex.org/keywords/mathematics
keywords[2].score	0.3911944627761841
keywords[2].display_name	Mathematics
keywords[3].id	https://openalex.org/keywords/computer-science
keywords[3].score	0.3168795704841614
keywords[3].display_name	Computer science
keywords[4].id	https://openalex.org/keywords/artificial-intelligence
keywords[4].score	0.2393786907196045
keywords[4].display_name	Artificial intelligence
language	en
locations[0].id	pmh:oai:arXiv.org:2403.09456
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license	cc-by
locations[0].pdf_url	https://arxiv.org/pdf/2403.09456
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2403.09456
locations[1].id	doi:10.48550/arxiv.2403.09456
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2403.09456
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5086808820
authorships[0].author.orcid	https://orcid.org/0000-0002-9215-0166
authorships[0].author.display_name	Jagdeep Singh
authorships[0].author_position	first
authorships[0].raw_author_name	Singh, Jagdeep
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5053879576
authorships[1].author.orcid	https://orcid.org/0000-0003-2672-6857
authorships[1].author.display_name	Vaidy Sivaraman
authorships[1].author_position	last
authorships[1].raw_author_name	Sivaraman, Vaidy
authorships[1].is_corresponding	False
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2403.09456
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Edge-apexing in hereditary classes of graphs
has_fulltext	True
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10374
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9987000226974487
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Advanced Graph Theory Research
related_works	https://openalex.org/W2748952813, https://openalex.org/W1979597421, https://openalex.org/W2007980826, https://openalex.org/W2061531152, https://openalex.org/W3002753104, https://openalex.org/W2077600819, https://openalex.org/W2142036596, https://openalex.org/W2072657027, https://openalex.org/W2600246793, https://openalex.org/W4238204885
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2403.09456
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license	cc-by
best_oa_location.pdf_url	https://arxiv.org/pdf/2403.09456
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2403.09456
primary_location.id	pmh:oai:arXiv.org:2403.09456
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license	cc-by
primary_location.pdf_url	https://arxiv.org/pdf/2403.09456
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2403.09456
publication_date	2024-03-14
publication_year	2024
referenced_works_count	0
abstract_inverted_index.8	114
abstract_inverted_index.A	0
abstract_inverted_index.a	45
abstract_inverted_index.We	16, 35
abstract_inverted_index.an	93
abstract_inverted_index.as	92
abstract_inverted_index.at	26
abstract_inverted_index.be	71
abstract_inverted_index.by	18, 113, 120
abstract_inverted_index.do	86
abstract_inverted_index.if	8, 44
abstract_inverted_index.in	33
abstract_inverted_index.is	5, 10, 39
abstract_inverted_index.it	9
abstract_inverted_index.of	3, 22, 62, 65, 99, 108, 118
abstract_inverted_index.so	56
abstract_inverted_index.$G$	68
abstract_inverted_index.For	96
abstract_inverted_index.The	59
abstract_inverted_index.all	66, 117
abstract_inverted_index.and	41, 77, 115
abstract_inverted_index.are	25, 81
abstract_inverted_index.can	70
abstract_inverted_index.has	49
abstract_inverted_index.not	87
abstract_inverted_index.one	28
abstract_inverted_index.our	102
abstract_inverted_index.the	20, 83, 89, 97, 106
abstract_inverted_index.away	30
abstract_inverted_index.does	57
abstract_inverted_index.edge	29
abstract_inverted_index.from	31, 73
abstract_inverted_index.have	88
abstract_inverted_index.main	103
abstract_inverted_index.many	51
abstract_inverted_index.most	27
abstract_inverted_index.note	36
abstract_inverted_index.path	91
abstract_inverted_index.such	109
abstract_inverted_index.that	24, 37, 43, 69, 85
abstract_inverted_index.them	119
abstract_inverted_index.then	55
abstract_inverted_index.$K_1$	74
abstract_inverted_index.being	32
abstract_inverted_index.class	1, 21, 47, 61, 98
abstract_inverted_index.finds	116
abstract_inverted_index.order	107
abstract_inverted_index.prove	42
abstract_inverted_index.under	12
abstract_inverted_index.using	75
abstract_inverted_index.bounds	105
abstract_inverted_index.called	6
abstract_inverted_index.closed	11
abstract_inverted_index.denote	17
abstract_inverted_index.graphs	4, 23, 67, 84
abstract_inverted_index.result	104
abstract_inverted_index.taking	13
abstract_inverted_index.union.	79
abstract_inverted_index.induced	14, 53, 94, 111
abstract_inverted_index.search.	122
abstract_inverted_index.Cographs	80
abstract_inverted_index.cographs	63, 101
abstract_inverted_index.computer	121
abstract_inverted_index.consists	64
abstract_inverted_index.disjoint	78
abstract_inverted_index.finitely	50
abstract_inverted_index.edge-apex	100
abstract_inverted_index.forbidden	52, 110
abstract_inverted_index.generated	72
abstract_inverted_index.precisely	82
abstract_inverted_index.subgraph.	95
abstract_inverted_index.subgraphs	112
abstract_inverted_index.$4$-vertex	90
abstract_inverted_index.$G^{epex}$	19, 38
abstract_inverted_index.hereditary	7, 40, 46, 60
abstract_inverted_index.subgraphs,	54
abstract_inverted_index.subgraphs.	15
abstract_inverted_index.$G^{epex}$.	58
abstract_inverted_index.$\mathcal{G}$	2, 48
abstract_inverted_index.$\mathcal{G}$.	34
abstract_inverted_index.complementation	76
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	2
citation_normalized_percentile