Computing a 3-role assignment is polynomial-time solvable on complementary prisms
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917585564467200 |
|---|---|
| author | Castonguay, Diane Dias, Elisângela S. Mesquita, Fernanda N. Nascimento, Julliano R. |
| author_facet | Castonguay, Diane Dias, Elisângela S. Mesquita, Fernanda N. Nascimento, Julliano R. |
| contents | A $r$-role assignment of a simple graph $G$ is an assignment of $r$ distinct roles to the vertices of $G$, such that two vertices with the same role have the same set of roles assigned to related vertices. Furthermore, a specific $r$-role assignment defines a role graph, in which the vertices are the distinct $r$ roles, and there is an edge between two roles whenever there are two related vertices in the graph $G$ that correspond to these roles. We consider complementary prisms, which are graphs formed from the disjoint union of the graph with its respective complement, adding the edges of a perfect matching between their corresponding vertices. In this work, we characterize the complementary prisms that do not admit a $3$-role assignment. We highlight that all of them are complementary prisms of disconnected bipartite graphs. Moreover, using our findings, we show that the problem of deciding whether a complementary prism has a $3$-role assignment can be solved in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_06068 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing a 3-role assignment is polynomial-time solvable on complementary prisms Castonguay, Diane Dias, Elisângela S. Mesquita, Fernanda N. Nascimento, Julliano R. Discrete Mathematics Combinatorics 05C15, 05C75, 05C76 G.2.2 A $r$-role assignment of a simple graph $G$ is an assignment of $r$ distinct roles to the vertices of $G$, such that two vertices with the same role have the same set of roles assigned to related vertices. Furthermore, a specific $r$-role assignment defines a role graph, in which the vertices are the distinct $r$ roles, and there is an edge between two roles whenever there are two related vertices in the graph $G$ that correspond to these roles. We consider complementary prisms, which are graphs formed from the disjoint union of the graph with its respective complement, adding the edges of a perfect matching between their corresponding vertices. In this work, we characterize the complementary prisms that do not admit a $3$-role assignment. We highlight that all of them are complementary prisms of disconnected bipartite graphs. Moreover, using our findings, we show that the problem of deciding whether a complementary prism has a $3$-role assignment can be solved in polynomial time. |
| title | Computing a 3-role assignment is polynomial-time solvable on complementary prisms |
| topic | Discrete Mathematics Combinatorics 05C15, 05C75, 05C76 G.2.2 |
| url | https://arxiv.org/abs/2402.06068 |