No label defined (Q4943288)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1416067
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1416067 |
Statements
23 October 2000
0 references
direct product
0 references
adjacency matrix
0 references
regular bipartite graphs
0 references
0.7821526527404785
0 references
0.7664654850959778
0 references
0.7538583278656006
0 references
0.7376964092254639
0 references
A balanced bipartite graph may have an automorphism that maps the vertices of one part to the vertices of the other. Such graphs have a symmetric bipartite adjacency matrix. It is known that the tensor or direct product \(G\otimes H\) of two graphs \(G\) and \(H\) is the graph with the vertex set \(V(G)\otimes V(H)\) and the edge set consisting of those pairs of vertices \((g,h)\), \((g',h')\) where \(g\) is adjacent to \(g'\) and \(h\) is adjacent to \(h'\). For example, the product \(K_2\otimes G\) is a balanced bipartite graph for any graph \(G\) and where \(K_2\) is a complete graph on two vertices. \(K_2\otimes G\) need not be regular. In the present paper the authors prove that a class of balanced bipartite graphs may be represented by such a product. They establish the following result (Theorem 1): The following conditions on a bipartite graph \(H\) are equivalent: (1) \(H\) has a symmetric bipartite adjacency matrix with constant row-sums. (2) \(H\) may be written as \(K_2\otimes G\) for some regular graph \(G\) (where \(G\) may have loops). (3) \(H\) is regular and has an involution that maps vertices in one part of \(H\) to vertices in the other part. A weaker result for non-regular balanced bipartite graphs is given by Corollary 2. The authors show by an construction that there exist regular bipartite graphs for all even \(n\geq 6\) and degree three for which the three conditions of Theorem 1 are false; the smallest counterexample is presented by a figure.
0 references