Atribuição de papéis em alguns produtos de grafos
Nenhuma Miniatura disponível
Data
2022-06-24
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
During the pandemic, due to the new coronavirus (COVID-19), the use of social networks was
enhanced by social distancing and the need to stay connected, generating a gigantic volume
of data. In order to extract information, graphs constitute a powerful modeling tool in which
the vertices represent individuals and the edges represent relationships between them. In
1991, Everett and Borgatti formalized the concept of role assignment under the name role
coloring. Thus, 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 in the
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. Research on role assignment and operations on graphs is scarce.
We showed a dichotomy for the r-role assignment problem for the Cartesian product. While
the Cartesian product of two graphs always admits a 2-role assignment, the problem remains
NP-complete for any fixed r ≥ 3. The complementary prism arises from the complementary
product, introduced by Haynes, Henning and Van Der Merwe in 2019, which is a
generalization of the Cartesian product. Complementary prisms admits a 2-role assignment,
with the exception of the complementary prism of a path with three vertices. We verified that
the complementary prisms admits a 3-role assignment, with the exception of the
complementary prism of some not connected bipartite graphs. Next, we showed that the
related problem can be solved in linear time. Finally, we conjecture that, for r ≥ 3 the problem
of (r+1)-role assignment to complementary prisms is NP-complete. In this sense, we consider
the role graph K'_{1,r} which is the bipartite graph K_{1,r} with a loop at the vertex of
degree r and we highlight that the problem of deciding whether a prism complement has a
(r+1)-role assignment, when the role graph is K'_{1,r}, it is NP-complete.
Descrição
Palavras-chave
Citação
MESQUITA, F. N. Atribuição de papéis em alguns produtos de grafos. 2022. 130 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2022.