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

      0 references
      0 references
      0 references
      23 October 2000
      0 references
      direct product
      0 references
      adjacency matrix
      0 references
      regular bipartite graphs
      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

      Identifiers