TY - JOUR
T1 - Algorithm to check the existence of H for a given G such that A (G) A (H) is graphical
AU - Bhat, K. Arathi
AU - Sudhakara, G.
AU - Vinay, M.
N1 - Publisher Copyright:
© 2022 World Scientific Publishing Company.
PY - 2022/7/1
Y1 - 2022/7/1
N2 - A matrix with entries 0, 1 is graphical if it is symmetric and all its diagonal entries are zero. Let G1, G2 and G3 be graphs defined on the same set of vertices. The graph G3 is said to be the matrix product of graphs G1 and G2, if A(G1)A(G2) = A(G3), where A(Gi) is the adjacency matrix of the graph Gi, 1 ≤ i ≤ 3. In such a case, we say that G1 and G2 are companions of each other. The main purpose of this paper is to design an algorithm to check whether a given graph G has a companion. We derive conditions on n and m so that the generalized wheel graph, denoted by Wm,n, has a companion and also show that the mth power of the path graph Pn has no companion. Finally, we indicate a possible application of the algorithm in a problem of coloring of edges of the complete graph Kn.
AB - A matrix with entries 0, 1 is graphical if it is symmetric and all its diagonal entries are zero. Let G1, G2 and G3 be graphs defined on the same set of vertices. The graph G3 is said to be the matrix product of graphs G1 and G2, if A(G1)A(G2) = A(G3), where A(Gi) is the adjacency matrix of the graph Gi, 1 ≤ i ≤ 3. In such a case, we say that G1 and G2 are companions of each other. The main purpose of this paper is to design an algorithm to check whether a given graph G has a companion. We derive conditions on n and m so that the generalized wheel graph, denoted by Wm,n, has a companion and also show that the mth power of the path graph Pn has no companion. Finally, we indicate a possible application of the algorithm in a problem of coloring of edges of the complete graph Kn.
UR - http://www.scopus.com/inward/record.url?scp=85111312529&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85111312529&partnerID=8YFLogxK
U2 - 10.1142/S1793830921501597
DO - 10.1142/S1793830921501597
M3 - Article
AN - SCOPUS:85111312529
SN - 1793-8309
VL - 14
JO - Discrete Mathematics, Algorithms and Applications
JF - Discrete Mathematics, Algorithms and Applications
IS - 5
M1 - 2150159
ER -