Permanent of the Laplacian matrix of trees with a given matching (Q1107543): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 02:02, 31 January 2024

scientific article
Language Label Description Also known as
English
Permanent of the Laplacian matrix of trees with a given matching
scientific article

    Statements

    Permanent of the Laplacian matrix of trees with a given matching (English)
    0 references
    0 references
    1986
    0 references
    Let \(G=(V,E)\) be an arbitrary graph, and \(d_ i>0\) be the degree of the vertex \(v_ i\in V\). D(G) denotes the diagonal matrix whose (i,i)-entry is \(d_ i\), and A(G) denotes the adjacency matrix of the graph G. The matrix \(L(G)=D(G)-A(G)\) will be called the Laplacian matrix of the graph G. Brualdi and the author have obtained bounds for PerL(G) where PerL(G) is the permanent of the matrix L(G) and G is a bipartite graph. They have also introduced the notion of the Laplacian ratio \(\pi (G)=PerL(G)/d_ 1d_ 2\cdot \cdot \cdot d_ n\) and obtained a lower bound for \(\pi\) (G) where G is a bipartite graph. In this work upper and lower bounds are obtained for \(\pi\) (T), namely \(\pi (T)\geq \pi (C_ k)\) and \(\pi\) (T)\(\leq 2\) k, where T is a tree, k is the maximal number of independent edges of T, and \(C_ k\) is the tree obtained by adjoining a pendant edge to each vertex of the path \(P_ k\).
    0 references
    0 references
    upper bounds
    0 references
    adjacency matrix
    0 references
    Laplacian matrix
    0 references
    permanent
    0 references
    bipartite graph
    0 references
    lower bounds
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references