Graph homomorphisms and components of quotient graphs

被引:2
作者
Bubboloni, Daniela [1 ]
机构
[1] Univ Firenze, Dipartimento Matemat & Informat U Dini, Viale Morgagni 67-A, I-50134 Florence, Italy
来源
RENDICONTI DEL SEMINARIO MATEMATICO DELLA UNIVERSITA DI PADOVA | 2017年 / 138卷
关键词
Graph homomorphism; quotient graph; components; power graphs; COMPLEXITY;
D O I
10.4171/RSMUP/138-2
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We study how the number c(X) of components of a graph X can be expressed through the number and properties of the components of a quotient graph X/similar to. We partially rely on classic qualifications of graph homomorphisms such as locally constrained homomorphisms and on the concept of equitable partition and orbit partition. We introduce the new definitions of pseudo-covering homomorphism and of component equitable partition, exhibiting interesting inclusions among the various classes of considered homomorphisms. As a consequence, we find a procedure for computing c(X) when the projection on the quotient X/similar to is pseudo-covering. That procedure becomes particularly easy to handle when the partition corresponding to X/similar to is an orbit partition.
引用
收藏
页码:39 / 60
页数:22
相关论文
共 16 条
[1]   Power Graphs: A Survey [J].
Abawajy, Jemal ;
Kelarev, Andrei ;
Chowdhury, Morshed .
ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2013, 1 (02) :125-147
[2]   ENDOMORPHISM SPECTRA OF GRAPHS [J].
BOTTCHER, M ;
KNAUER, U .
DISCRETE MATHEMATICS, 1992, 109 (1-3) :45-57
[3]   On some graphs associated with the finite alternating groups [J].
Bubboloni, D. ;
Iranmanesh, Mohammad A. ;
Shaker, S. M. .
COMMUNICATIONS IN ALGEBRA, 2017, 45 (12) :5355-5373
[4]   Quotient graphs for power graphs [J].
Bubboloni, Daniela ;
Iranmanesh, Mohammad A. ;
Shaker, Seyed M. .
RENDICONTI DEL SEMINARIO MATEMATICO DELLA UNIVERSITA DI PADOVA, 2017, 138 :61-89
[5]  
Diestel Reinhard, 2012, Graduate Texts in Mathematics, V173
[6]   ROLE COLORING A GRAPH [J].
EVERETT, MG ;
BORGATTI, S .
MATHEMATICAL SOCIAL SCIENCES, 1991, 21 (02) :183-188
[7]   A complete complexity classification of the role assignment problem [J].
Fiala, J ;
Paulusma, D .
THEORETICAL COMPUTER SCIENCE, 2005, 349 (01) :67-81
[8]  
FIALA J., 2002, Discuss. Math. Graph Theory, V22, P89
[9]   Locally constrained graph homomorphisms-structure, complexity, and applications [J].
Fiala, Jiri ;
Kratochvil, Jan .
COMPUTER SCIENCE REVIEW, 2008, 2 (02) :97-111
[10]  
Godsil C., 1993, Algebraic Combinatorics, V6