On Separating Path and Tree Systems in Graphs Article Swipe

PDF

Ahmad Biniaz , Prosenjit Bose , Jean-Lou De Carufel , Anil Maheshwari , Babak Miraftab , Saeed Odak , Michiel Smid , Shakhar Smorodinsky , Yelena Yuditsky ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.46298/dmtcs.12743

We explore the concept of separating systems of vertex sets of graphs. A separating system of a set $X$ is a collection of subsets of $X$ such that for any pair of distinct elements in $X$, there exists a set in the separating system that contains exactly one of the two elements. A separating system of the vertex set of a graph $G$ is called a vertex-separating path (tree) system of $G$ if the elements of the separating system are paths (trees) in the graph $G$. In this paper, we focus on the size of the smallest vertex-separating path (tree) system for different types of graphs, including trees, grids, and maximal outerplanar graphs. Comment: 23 page, 3 figures dmtcs final version

Related Topics

Concepts

Mathematics Combinatorics Path (computing) Tree (set theory) Computer science Programming language

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.46298/dmtcs.12743
PDF: https://dmtcs.episciences.org/15665/pdf
OA Status: diamond
Cited By: 1
Related Works: 10
OpenAlex ID: https://openalex.org/W4410527555

All OpenAlex metadata

Raw OpenAlex JSON

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

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.46298/dmtcs.12743

Digital Object Identifier
Title: On Separating Path and Tree Systems in Graphs

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2025

Year of publication
Publication date: 2025-05-20

Full publication date if available
Authors: Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari, Babak Miraftab, Saeed Odak, Michiel Smid, Shakhar Smorodinsky, Yelena Yuditsky

List of authors in order
Landing page: https://doi.org/10.46298/dmtcs.12743

Publisher landing page
PDF URL: https://dmtcs.episciences.org/15665/pdf

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: diamond

Open access status per OpenAlex
OA URL: https://dmtcs.episciences.org/15665/pdf

Direct OA link when available
Concepts: Mathematics, Combinatorics, Path (computing), Tree (set theory), Computer science, Programming language

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

Total citation count in OpenAlex
Citations by year (recent): 2025: 1

Per-year citation counts (last 5 years)
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4410527555
doi	https://doi.org/10.46298/dmtcs.12743
ids.doi	https://doi.org/10.46298/dmtcs.12743
ids.openalex	https://openalex.org/W4410527555
fwci	5.32681814
type	article
title	On Separating Path and Tree Systems in Graphs
biblio.issue	Graph Theory
biblio.volume	vol. 27:2
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11106
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9973999857902527
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1711
topics[0].subfield.display_name	Signal Processing
topics[0].display_name	Data Management and Algorithms
topics[1].id	https://openalex.org/T10374
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9943000078201294
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	Advanced Graph Theory Research
topics[2].id	https://openalex.org/T12292
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9927999973297119
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1707
topics[2].subfield.display_name	Computer Vision and Pattern Recognition
topics[2].display_name	Graph Theory and Algorithms
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C33923547
concepts[0].level	0
concepts[0].score	0.8736143112182617
concepts[0].wikidata	https://www.wikidata.org/wiki/Q395
concepts[0].display_name	Mathematics
concepts[1].id	https://openalex.org/C114614502
concepts[1].level	1
concepts[1].score	0.632394552230835
concepts[1].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[1].display_name	Combinatorics
concepts[2].id	https://openalex.org/C2777735758
concepts[2].level	2
concepts[2].score	0.6267688870429993
concepts[2].wikidata	https://www.wikidata.org/wiki/Q817765
concepts[2].display_name	Path (computing)
concepts[3].id	https://openalex.org/C113174947
concepts[3].level	2
concepts[3].score	0.5773869156837463
concepts[3].wikidata	https://www.wikidata.org/wiki/Q2859736
concepts[3].display_name	Tree (set theory)
concepts[4].id	https://openalex.org/C41008148
concepts[4].level	0
concepts[4].score	0.07469776272773743
concepts[4].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[4].display_name	Computer science
concepts[5].id	https://openalex.org/C199360897
concepts[5].level	1
concepts[5].score	0.0
concepts[5].wikidata	https://www.wikidata.org/wiki/Q9143
concepts[5].display_name	Programming language
keywords[0].id	https://openalex.org/keywords/mathematics
keywords[0].score	0.8736143112182617
keywords[0].display_name	Mathematics
keywords[1].id	https://openalex.org/keywords/combinatorics
keywords[1].score	0.632394552230835
keywords[1].display_name	Combinatorics
keywords[2].id	https://openalex.org/keywords/path
keywords[2].score	0.6267688870429993
keywords[2].display_name	Path (computing)
keywords[3].id	https://openalex.org/keywords/tree
keywords[3].score	0.5773869156837463
keywords[3].display_name	Tree (set theory)
keywords[4].id	https://openalex.org/keywords/computer-science
keywords[4].score	0.07469776272773743
keywords[4].display_name	Computer science
language	en
locations[0].id	doi:10.46298/dmtcs.12743
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S200334879
locations[0].source.issn	1365-8050, 1462-7264
locations[0].source.type	journal
locations[0].source.is_oa	True
locations[0].source.issn_l	1365-8050
locations[0].source.is_core	True
locations[0].source.is_in_doaj	True
locations[0].source.display_name	Discrete Mathematics & Theoretical Computer Science
locations[0].source.host_organization	https://openalex.org/P4328141799
locations[0].source.host_organization_name	French association
locations[0].source.host_organization_lineage	https://openalex.org/P4328141799
locations[0].source.host_organization_lineage_names	French association
locations[0].license	cc-by
locations[0].pdf_url	https://dmtcs.episciences.org/15665/pdf
locations[0].version	publishedVersion
locations[0].raw_type	journal-article
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Discrete Mathematics & Theoretical Computer Science
locations[0].landing_page_url	https://doi.org/10.46298/dmtcs.12743
locations[1].id	pmh:oai:dipot.ulb.ac.be:2013/393181
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306401063
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	False
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	Dépôt institutionnel de l'Université libre de Bruxelles (Université Libre de Bruxelles)
locations[1].source.host_organization	https://openalex.org/I132053463
locations[1].source.host_organization_name	Université Libre de Bruxelles
locations[1].source.host_organization_lineage	https://openalex.org/I132053463
locations[1].license	other-oa
locations[1].pdf_url
locations[1].version	submittedVersion
locations[1].raw_type	info:ulb-repo/semantics/openurl/article
locations[1].license_id	https://openalex.org/licenses/other-oa
locations[1].is_accepted	False
locations[1].is_published	False
locations[1].raw_source_name	Discrete mathematics and theoretical computer science, 272
locations[1].landing_page_url	http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/393181
locations[2].id	pmh:oai:doaj.org/article:d37496da63834470bd83c4efe0533512
locations[2].is_oa	False
locations[2].source.id	https://openalex.org/S4306401280
locations[2].source.issn
locations[2].source.type	repository
locations[2].source.is_oa	False
locations[2].source.issn_l
locations[2].source.is_core	False
locations[2].source.is_in_doaj	False
locations[2].source.display_name	DOAJ (DOAJ: Directory of Open Access Journals)
locations[2].source.host_organization
locations[2].source.host_organization_name
locations[2].license
locations[2].pdf_url
locations[2].version	submittedVersion
locations[2].raw_type	article
locations[2].license_id
locations[2].is_accepted	False
locations[2].is_published	False
locations[2].raw_source_name	Discrete Mathematics & Theoretical Computer Science, Vol vol. 27:2, Iss Graph Theory (2025)
locations[2].landing_page_url	https://doaj.org/article/d37496da63834470bd83c4efe0533512
indexed_in	crossref, doaj
authorships[0].author.id	https://openalex.org/A5015212072
authorships[0].author.orcid	https://orcid.org/0000-0002-6396-4494
authorships[0].author.display_name	Ahmad Biniaz
authorships[0].author_position	first
authorships[0].raw_author_name	Ahmad Biniaz
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5013674788
authorships[1].author.orcid	https://orcid.org/0000-0002-8906-0573
authorships[1].author.display_name	Prosenjit Bose
authorships[1].author_position	middle
authorships[1].raw_author_name	Prosenjit Bose
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5042440491
authorships[2].author.orcid	https://orcid.org/0000-0002-6734-8234
authorships[2].author.display_name	Jean-Lou De Carufel
authorships[2].author_position	middle
authorships[2].raw_author_name	Jean-Lou De Carufel
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5103136561
authorships[3].author.orcid	https://orcid.org/0000-0002-1274-4598
authorships[3].author.display_name	Anil Maheshwari
authorships[3].author_position	middle
authorships[3].raw_author_name	Anil Maheshwari
authorships[3].is_corresponding	False
authorships[4].author.id	https://openalex.org/A5038599776
authorships[4].author.orcid	https://orcid.org/0000-0001-8232-2502
authorships[4].author.display_name	Babak Miraftab
authorships[4].author_position	middle
authorships[4].raw_author_name	Babak Miraftab
authorships[4].is_corresponding	False
authorships[5].author.id	https://openalex.org/A5082659766
authorships[5].author.orcid
authorships[5].author.display_name	Saeed Odak
authorships[5].author_position	middle
authorships[5].raw_author_name	Saeed Odak
authorships[5].is_corresponding	False
authorships[6].author.id	https://openalex.org/A5108374265
authorships[6].author.orcid
authorships[6].author.display_name	Michiel Smid
authorships[6].author_position	middle
authorships[6].raw_author_name	Michiel Smid
authorships[6].is_corresponding	False
authorships[7].author.id	https://openalex.org/A5071731808
authorships[7].author.orcid	https://orcid.org/0000-0003-3038-6955
authorships[7].author.display_name	Shakhar Smorodinsky
authorships[7].author_position	middle
authorships[7].raw_author_name	Shakhar Smorodinsky
authorships[7].is_corresponding	False
authorships[8].author.id	https://openalex.org/A5073143034
authorships[8].author.orcid	https://orcid.org/0000-0002-6467-3437
authorships[8].author.display_name	Yelena Yuditsky
authorships[8].author_position	last
authorships[8].raw_author_name	Yelena Yuditsky
authorships[8].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://dmtcs.episciences.org/15665/pdf
open_access.oa_status	diamond
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	On Separating Path and Tree Systems in Graphs
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T11106
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9973999857902527
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1711
primary_topic.subfield.display_name	Signal Processing
primary_topic.display_name	Data Management and Algorithms
related_works	https://openalex.org/W4391375266, 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/W2962838298, https://openalex.org/W2600246793
cited_by_count	1
counts_by_year[0].year	2025
counts_by_year[0].cited_by_count	1
locations_count	3
best_oa_location.id	doi:10.46298/dmtcs.12743
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S200334879
best_oa_location.source.issn	1365-8050, 1462-7264
best_oa_location.source.type	journal
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l	1365-8050
best_oa_location.source.is_core	True
best_oa_location.source.is_in_doaj	True
best_oa_location.source.display_name	Discrete Mathematics & Theoretical Computer Science
best_oa_location.source.host_organization	https://openalex.org/P4328141799
best_oa_location.source.host_organization_name	French association
best_oa_location.source.host_organization_lineage	https://openalex.org/P4328141799
best_oa_location.source.host_organization_lineage_names	French association
best_oa_location.license	cc-by
best_oa_location.pdf_url	https://dmtcs.episciences.org/15665/pdf
best_oa_location.version	publishedVersion
best_oa_location.raw_type	journal-article
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	Discrete Mathematics & Theoretical Computer Science
best_oa_location.landing_page_url	https://doi.org/10.46298/dmtcs.12743
primary_location.id	doi:10.46298/dmtcs.12743
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S200334879
primary_location.source.issn	1365-8050, 1462-7264
primary_location.source.type	journal
primary_location.source.is_oa	True
primary_location.source.issn_l	1365-8050
primary_location.source.is_core	True
primary_location.source.is_in_doaj	True
primary_location.source.display_name	Discrete Mathematics & Theoretical Computer Science
primary_location.source.host_organization	https://openalex.org/P4328141799
primary_location.source.host_organization_name	French association
primary_location.source.host_organization_lineage	https://openalex.org/P4328141799
primary_location.source.host_organization_lineage_names	French association
primary_location.license	cc-by
primary_location.pdf_url	https://dmtcs.episciences.org/15665/pdf
primary_location.version	publishedVersion
primary_location.raw_type	journal-article
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Discrete Mathematics & Theoretical Computer Science
primary_location.landing_page_url	https://doi.org/10.46298/dmtcs.12743
publication_date	2025-05-20
publication_year	2025
referenced_works_count	0
abstract_inverted_index.3	116
abstract_inverted_index.A	12, 52
abstract_inverted_index.a	16, 20, 38, 60, 65
abstract_inverted_index.23	114
abstract_inverted_index.In	86
abstract_inverted_index.We	0
abstract_inverted_index.if	72
abstract_inverted_index.in	34, 40, 82
abstract_inverted_index.is	19, 63
abstract_inverted_index.of	4, 7, 10, 15, 22, 24, 31, 48, 55, 59, 70, 75, 94, 104
abstract_inverted_index.on	91
abstract_inverted_index.we	89
abstract_inverted_index.$G$	62, 71
abstract_inverted_index.$X$	18, 25
abstract_inverted_index.and	109
abstract_inverted_index.any	29
abstract_inverted_index.are	79
abstract_inverted_index.for	28, 101
abstract_inverted_index.one	47
abstract_inverted_index.set	17, 39, 58
abstract_inverted_index.the	2, 41, 49, 56, 73, 76, 83, 92, 95
abstract_inverted_index.two	50
abstract_inverted_index.$G$.	85
abstract_inverted_index.$X$,	35
abstract_inverted_index.pair	30
abstract_inverted_index.path	67, 98
abstract_inverted_index.sets	9
abstract_inverted_index.size	93
abstract_inverted_index.such	26
abstract_inverted_index.that	27, 44
abstract_inverted_index.this	87
abstract_inverted_index.dmtcs	118
abstract_inverted_index.final	119
abstract_inverted_index.focus	90
abstract_inverted_index.graph	61, 84
abstract_inverted_index.page,	115
abstract_inverted_index.paths	80
abstract_inverted_index.there	36
abstract_inverted_index.types	103
abstract_inverted_index.(tree)	68, 99
abstract_inverted_index.called	64
abstract_inverted_index.exists	37
abstract_inverted_index.grids,	108
abstract_inverted_index.paper,	88
abstract_inverted_index.system	14, 43, 54, 69, 78, 100
abstract_inverted_index.trees,	107
abstract_inverted_index.vertex	8, 57
abstract_inverted_index.(trees)	81
abstract_inverted_index.concept	3
abstract_inverted_index.exactly	46
abstract_inverted_index.explore	1
abstract_inverted_index.figures	117
abstract_inverted_index.graphs,	105
abstract_inverted_index.graphs.	11, 112
abstract_inverted_index.maximal	110
abstract_inverted_index.subsets	23
abstract_inverted_index.systems	6
abstract_inverted_index.version	120
abstract_inverted_index.Comment:	113
abstract_inverted_index.contains	45
abstract_inverted_index.distinct	32
abstract_inverted_index.elements	33, 74
abstract_inverted_index.smallest	96
abstract_inverted_index.different	102
abstract_inverted_index.elements.	51
abstract_inverted_index.including	106
abstract_inverted_index.collection	21
abstract_inverted_index.separating	5, 13, 42, 53, 77
abstract_inverted_index.outerplanar	111
abstract_inverted_index.vertex-separating	66, 97
cited_by_percentile_year.max	95
cited_by_percentile_year.min	91
countries_distinct_count	0
institutions_distinct_count	9
citation_normalized_percentile.value	0.88511783
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	True