The permanent of the Laplacian matrix of a bipartite graph (Q3739149)

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 3972893
Language Label Description Also known as
default for all languages
No label defined
    English
    The permanent of the Laplacian matrix of a bipartite graph
    scientific article; zbMATH DE number 3972893

      Statements

      0 references
      1986
      0 references
      permanent
      0 references
      Laplacian matrix
      0 references
      bipartite graph
      0 references
      The permanent of the Laplacian matrix of a bipartite graph (English)
      0 references
      Lower bounds for the permanent of the Laplacian matrix L(G) of a bipartite graph G with v vertices and e edges are proved: per L(G)\(\geq 3e-v+1\), per L(G)\(\geq 2(2e-v+1)\). Equality is attained iff G is the star. The combinatorial nature of per L(G) is demonstrated at its expansion by means of a certain collection of subgraphs of G.
      0 references

      Identifiers