Algorithm to check the existence of H for a given G such that A (G) A (H) is graphical

K. Arathi Bhat, G. Sudhakara, M. Vinay

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Article number2150159
JournalDiscrete Mathematics, Algorithms and Applications
Issue number5
Publication statusPublished - 01-07-2022

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Algorithm to check the existence of H for a given G such that A (G) A (H) is graphical'. Together they form a unique fingerprint.

Cite this