Word-Representability of Graphs with respect to Split Recomposition
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916080670212096 |
|---|---|
| author | Dwary, Tithi Krishna, K. V. |
| author_facet | Dwary, Tithi Krishna, K. V. |
| contents | In this work, we show that the class of word-representable graphs is closed under split recomposition and determine the representation number of the graph obtained by recomposing two word-representable graphs. Accordingly, we show that the class of parity graphs is word-representable. Further, we obtain a characteristic property by which the recomposition of comparability graphs is a comparability graph. Consequently, we also establish the permutation-representation number (prn) of the resulting comparability graph. We also introduce a subclass of comparability graphs, called prn-irreducible graphs. We provide a criterion such that the split recomposition of two prn-irreducible graphs is a comparability graph and determine the prn of the resultant graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_01954 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Word-Representability of Graphs with respect to Split Recomposition Dwary, Tithi Krishna, K. V. Discrete Mathematics Combinatorics 68R10, 68R15, 05C90, 06A07 In this work, we show that the class of word-representable graphs is closed under split recomposition and determine the representation number of the graph obtained by recomposing two word-representable graphs. Accordingly, we show that the class of parity graphs is word-representable. Further, we obtain a characteristic property by which the recomposition of comparability graphs is a comparability graph. Consequently, we also establish the permutation-representation number (prn) of the resulting comparability graph. We also introduce a subclass of comparability graphs, called prn-irreducible graphs. We provide a criterion such that the split recomposition of two prn-irreducible graphs is a comparability graph and determine the prn of the resultant graph. |
| title | Word-Representability of Graphs with respect to Split Recomposition |
| topic | Discrete Mathematics Combinatorics 68R10, 68R15, 05C90, 06A07 |
| url | https://arxiv.org/abs/2401.01954 |