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 -