Permanents of graphs with cut vertices

DOI10.1080/0308108031000106649MaRDI QIDQ4455141zbMATH OpenOpenAlexFDO

Authors Suk-Geun Hwang, Xiao-Dong Zhang

Publication date 16 March 2004

Published in Linear and Multilinear Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/0308108031000106649

zbMATH Keywords

adjacency matrixconvectivity

Mathematics Subject Classification ID

Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Determinants, permanents, traces, other special matrix functions (15A15)

Review text

We refer to the permanent of the adjacency matrix of a graph \(G\) more simply as the ``permanent of \(G\). The permanent of the complete graph \(K_n\) is \(\delta_n\), the \(n\)th derangement number. The authors begin by proving some elementary inequalities involving derangement numbers. These are then used in an inductive proof of the main theorem, which is this: The maximum permanent of a graph with \(n\) vertices and \(k\) cut vertices is \(\delta_{n-k}\) if \(k\) is even and \(\delta_{n-k-1}+2\delta_{n-k-2}\) if \(k\) is odd. Graphs achieving these bounds are characterized. It is also noted that the corresponding minimisation problem is trivial. On page 400, ``line graph should say ``path instead. My only other criticism is that I would have liked more discussion as to why the maximising graph \(G\) must be connected, why deletion of a cut vertex in \(G\) leaves only two components and why the blocks of \(G\) must be complete. These points, while plausible, do need some justification. To be sure, adding edges can never decrease the permanent so we may assume that each block is complete for the purposes of finding the maximum permanent. However, when characterising the graphs which achieve the maximum, it needs to be at least noted that every edge is contributing to the permanent. On the issue of connectivity, cut vertices are defined in this paper only for connected graphs, but no restriction to connected graphs is mentioned thereafter.

Recommendations

• Some analytical properties of the permanental polynomial of a graph.
• A lower bound on the maximum permanent in \(\Lambda_{n}^{k}\).
• On the permanental sum of graphs
• Maximising the permanent and complementary permanent of (0,1)-matrices with constant line sum
• Publication:4943290

Cited in

(11)

• On characteristic and permanent polynomials of a matrix
• Properties of the extended graph permanent
• The coefficients of the immanantal polynomial
• Parameterized complexity of determinant and permanent
• Permanent, determinant, and rank of bi-block graphs
• scientific article; zbMATH DE number 1990713 (Why is no real title available?)
• Permanents of almost regular complete bipartite graphs
• Further results on permanents of Laplacian matrices of trees
• Two problems on Laplacian ratios of trees
• Solution to an open problem on Laplacian ratio
• On the maximum Zagreb indices of graphs with \(k\) cut vertices

This page was built for publication: Permanents of graphs with cut vertices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4455141)