0
$\begingroup$

Let $G$ and $ H$ be two graphs on the same vertex set (i.e. $V(G)=V(H)$).

Suppose that $K$ is the graph with adjacency matrix $A_G\times A_H$, where $A_G$ and $A_H$ are adjacency matrix of $G$ and $H$, respectively.

Is it known that when $K$ is connected?

Improve this question
$\endgroup$
4
  • $\begingroup$ You should tell us what product you are using in computing $A_G \times A_H$. $\endgroup$
    – Gordon Royle
    Commented Oct 14 at 11:47
  • $\begingroup$ The usual product of matrices! Thanks $\endgroup$
    – khers
    Commented Oct 15 at 12:03
  • 2
    $\begingroup$ This will rarely be a symmetric 0/1-matrix with 0-diagonal so usually it just won’t be an adjacency matrix of any graph. $\endgroup$
    – Gordon Royle
    Commented Oct 15 at 15:35
  • $\begingroup$ Thanks for your help. I work with multiple graphs with possible loops. For these graphs, is it known? $\endgroup$
    – khers
    Commented Oct 16 at 16:03

1 Answer 1

Reset to default
1
$\begingroup$

(If we allow loops and multiple edges with the corresponding entry of the adjacency matrix being the number of such loops or edges, then any non-negative matrix may be interpreted as an adjacency matrix. Then, the product $A_{G}A_{H}$ can be interpreted as a graph. However, since the product of symmetric matrices is usually not symmetric, the product of adjacency matrices of undirected graphs will need to be interpreted as a directed graph. Since an undirected graph can be interpreted as a directed graph with all edges in both directions, directed graphs are assumed here.)

The interpretation of powers of an adjacency matrix in terms of walks can be generalized to consider the significance of the product $A_{G}A_{H}.$ We take one step on $G$ and then one step on $H$. Then $K$ has an edge from the initial vertex in $G$ of this "2-walk" to the final vertex in $H$, i.e., the directed edges of $K$ are $E(K)=\{ij~|~ik\in E(G)\wedge kj\in E(H)\}$.

In general, this won't be connected since it won't contain a path to/from the intermediate vertices $k$ unless they also end/begin another 2-walk. There will be no edges away from the neighborhood of common vertices of $G$ and $H$.

It is possible to have $K$ strongly-connected, e.g., if $G$ and $H$ are complete graphs, but weakly connected (underlying undirected graph is connected) is more likely and is assumed here.

It is possible to have $K$ weakly connected even if neither $G$ or$\ H$ are connected: Graph images

The criterion for the graph of an adjacency matrix to be strongly-connected is (Ref. 1) $(I+A)^{|V|-1}>0$ (all entries positive). The matrix for the underlying graph is the symmetric version, and so the test for weakly connected is $(I+A+A^{T})^{|V|-1}>0$. (These tests depend only on the locations of the zero entries and work for any non-negative matrices.)

1: R.A. Horn, C.R. Johnson, Matrix Analysis, Thm. 6.2.4, p. 362, Cambridge University Press, 1985.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Many thanks for your help $\endgroup$
    – khers
    Commented Oct 20 at 9:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .