Counting the Number of Domatic Partition of a Graph Article Swipe

PDF

‎Saeid Alikhani , Davood Bakhshesh , Nima Ghanbari ·

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

A subset of vertices $S$ of a graph $G$ is a dominating set if every vertex in $V \setminus S$ has at least one neighbor in $S$. A domatic partition is a partition of the vertices of a graph $G$ into disjoint dominating sets. The domatic number $d(G)$ is the maximum size of a domatic partition. Suppose that $dp(G,i)$ is the number of distinct domatic partition of $G$ with cardinality $i$. In this paper, we consider the generating function of $dp(G,i)$, i.e., $DP(G,x)=\sum_{i=1}^{d(G)}dp(G,i)x^i$ which we call it the domatic partition polynomial. We explore the domatic polynomial for trees, providing a quadratic time algorithm for its computation based on weak 2-coloring numbers. Our results include specific findings for paths and certain graph products, demonstrating practical applications of our theoretical framework.

Related Topics

Mathematics

Computer Science

Combinatorics

Concepts

Graph Partition (number theory) Mathematics Computer science Combinatorics

Metadata

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

All OpenAlex metadata

Raw OpenAlex JSON

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

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

Digital Object Identifier
Title: Counting the Number of Domatic Partition of a Graph

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-06-27

Full publication date if available
Authors: ‎Saeid Alikhani, Davood Bakhshesh, Nima Ghanbari

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

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

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/2407.00103

Direct OA link when available
Concepts: Graph, Partition (number theory), Mathematics, Computer science, Combinatorics

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/W4400267064
doi	https://doi.org/10.48550/arxiv.2407.00103
ids.doi	https://doi.org/10.48550/arxiv.2407.00103
ids.openalex	https://openalex.org/W4400267064
fwci
type	preprint
title	Counting the Number of Domatic Partition of a Graph
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.9983999729156494
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.9930999875068665
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/T11106
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9715999960899353
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1711
topics[2].subfield.display_name	Signal Processing
topics[2].display_name	Data Management and Algorithms
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C132525143
concepts[0].level	2
concepts[0].score	0.5558388233184814
concepts[0].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[0].display_name	Graph
concepts[1].id	https://openalex.org/C42812
concepts[1].level	2
concepts[1].score	0.4949600100517273
concepts[1].wikidata	https://www.wikidata.org/wiki/Q1082910
concepts[1].display_name	Partition (number theory)
concepts[2].id	https://openalex.org/C33923547
concepts[2].level	0
concepts[2].score	0.44375061988830566
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.39378997683525085
concepts[3].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[3].display_name	Computer science
concepts[4].id	https://openalex.org/C114614502
concepts[4].level	1
concepts[4].score	0.35116177797317505
concepts[4].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[4].display_name	Combinatorics
keywords[0].id	https://openalex.org/keywords/graph
keywords[0].score	0.5558388233184814
keywords[0].display_name	Graph
keywords[1].id	https://openalex.org/keywords/partition
keywords[1].score	0.4949600100517273
keywords[1].display_name	Partition (number theory)
keywords[2].id	https://openalex.org/keywords/mathematics
keywords[2].score	0.44375061988830566
keywords[2].display_name	Mathematics
keywords[3].id	https://openalex.org/keywords/computer-science
keywords[3].score	0.39378997683525085
keywords[3].display_name	Computer science
keywords[4].id	https://openalex.org/keywords/combinatorics
keywords[4].score	0.35116177797317505
keywords[4].display_name	Combinatorics
language	en
locations[0].id	pmh:oai:arXiv.org:2407.00103
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
locations[0].pdf_url	https://arxiv.org/pdf/2407.00103
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2407.00103
locations[1].id	doi:10.48550/arxiv.2407.00103
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.2407.00103
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5029127053
authorships[0].author.orcid	https://orcid.org/0000-0002-1801-203X
authorships[0].author.display_name	‎Saeid Alikhani
authorships[0].author_position	first
authorships[0].raw_author_name	Alikhani, Saeid
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5059391205
authorships[1].author.orcid	https://orcid.org/0000-0002-8883-8312
authorships[1].author.display_name	Davood Bakhshesh
authorships[1].author_position	middle
authorships[1].raw_author_name	Bakhshesh, Davood
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5046055715
authorships[2].author.orcid	https://orcid.org/0000-0001-5063-3461
authorships[2].author.display_name	Nima Ghanbari
authorships[2].author_position	last
authorships[2].raw_author_name	Ghanbari, Nima
authorships[2].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2407.00103
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Counting the Number of Domatic Partition of a Graph
has_fulltext	False
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.9983999729156494
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/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/W2600246793
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2407.00103
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
best_oa_location.pdf_url	https://arxiv.org/pdf/2407.00103
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
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/2407.00103
primary_location.id	pmh:oai:arXiv.org:2407.00103
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
primary_location.pdf_url	https://arxiv.org/pdf/2407.00103
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2407.00103
publication_date	2024-06-27
publication_year	2024
referenced_works_count	0
abstract_inverted_index.A	0, 27
abstract_inverted_index.a	6, 10, 31, 37, 53, 99
abstract_inverted_index.$V	17
abstract_inverted_index.In	71
abstract_inverted_index.S$	19
abstract_inverted_index.We	91
abstract_inverted_index.at	21
abstract_inverted_index.if	13
abstract_inverted_index.in	16, 25
abstract_inverted_index.is	9, 30, 48, 59
abstract_inverted_index.it	86
abstract_inverted_index.of	2, 5, 33, 36, 52, 62, 66, 79, 125
abstract_inverted_index.on	107
abstract_inverted_index.we	74, 84
abstract_inverted_index.$G$	8, 39, 67
abstract_inverted_index.$S$	4
abstract_inverted_index.Our	111
abstract_inverted_index.The	44
abstract_inverted_index.and	118
abstract_inverted_index.for	96, 103, 116
abstract_inverted_index.has	20
abstract_inverted_index.its	104
abstract_inverted_index.one	23
abstract_inverted_index.our	126
abstract_inverted_index.set	12
abstract_inverted_index.the	34, 49, 60, 76, 87, 93
abstract_inverted_index.$S$.	26
abstract_inverted_index.$i$.	70
abstract_inverted_index.call	85
abstract_inverted_index.into	40
abstract_inverted_index.size	51
abstract_inverted_index.that	57
abstract_inverted_index.this	72
abstract_inverted_index.time	101
abstract_inverted_index.weak	108
abstract_inverted_index.with	68
abstract_inverted_index.based	106
abstract_inverted_index.every	14
abstract_inverted_index.graph	7, 38, 120
abstract_inverted_index.i.e.,	81
abstract_inverted_index.least	22
abstract_inverted_index.paths	117
abstract_inverted_index.sets.	43
abstract_inverted_index.which	83
abstract_inverted_index.$d(G)$	47
abstract_inverted_index.number	46, 61
abstract_inverted_index.paper,	73
abstract_inverted_index.subset	1
abstract_inverted_index.trees,	97
abstract_inverted_index.vertex	15
abstract_inverted_index.Suppose	56
abstract_inverted_index.certain	119
abstract_inverted_index.domatic	28, 45, 54, 64, 88, 94
abstract_inverted_index.explore	92
abstract_inverted_index.include	113
abstract_inverted_index.maximum	50
abstract_inverted_index.results	112
abstract_inverted_index.consider	75
abstract_inverted_index.disjoint	41
abstract_inverted_index.distinct	63
abstract_inverted_index.findings	115
abstract_inverted_index.function	78
abstract_inverted_index.neighbor	24
abstract_inverted_index.numbers.	110
abstract_inverted_index.specific	114
abstract_inverted_index.vertices	3, 35
abstract_inverted_index.$dp(G,i)$	58
abstract_inverted_index.\setminus	18
abstract_inverted_index.algorithm	102
abstract_inverted_index.partition	29, 32, 65, 89
abstract_inverted_index.practical	123
abstract_inverted_index.products,	121
abstract_inverted_index.providing	98
abstract_inverted_index.quadratic	100
abstract_inverted_index.$dp(G,i)$,	80
abstract_inverted_index.2-coloring	109
abstract_inverted_index.dominating	11, 42
abstract_inverted_index.framework.	128
abstract_inverted_index.generating	77
abstract_inverted_index.partition.	55
abstract_inverted_index.polynomial	95
abstract_inverted_index.cardinality	69
abstract_inverted_index.computation	105
abstract_inverted_index.polynomial.	90
abstract_inverted_index.theoretical	127
abstract_inverted_index.applications	124
abstract_inverted_index.demonstrating	122
abstract_inverted_index.$DP(G,x)=\sum_{i=1}^{d(G)}dp(G,i)x^i$	82
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
citation_normalized_percentile