$\mathcal{B}$-Partitions, determinant and permanent of graphs

Document Type : Research Paper

Authors

1 Department of Mathematics, Indian Institute of Technology Jodhpur, Jodhpur, India

2 Stat-Math Unit, ISI Delhi

Abstract

Let $G$ be a graph (directed or undirected) having $k$ number of blocks $B_1, B_2,\ldots,B_k$. A $\mathcal{B}$-partition of $G$ is a partition consists of $k$ vertex-disjoint subgraph $(\hat{B_1},\hat{B_1},\ldots,\hat{B_k})$ such that $\hat{B}_i$ is an induced subgraph of $B_i$ for $i=1, 2,\ldots,k.$ The terms $\prod_{i=1}^{k}\det(\hat{B}_i),\ \prod_{i=1}^{k}\text{per}(\hat{B}_i)$ represent the det-summands and the per-summands, respectively, corresponding to the $\mathcal{B}$-partition $(\hat{B_1},\hat{B_1},\ldots,\hat{B_k})$. The determinant (permanent) of a graph having no loops on its cut-vertices is equal to the summation of the det-summands (per-summands), corresponding to all possible $\mathcal{B}$-partitions. In this paper, we calculate the determinant and the permanent of classes of graphs such as block graph, block graph with negatives cliques, signed unicyclic graph, mixed complete graph, negative mixed complete graph, and star mixed block graphs.

Keywords

Main Subjects

References

[1] B. D. Acharya, Spectral criterion for cycle balance in networks, J. Graph Theory, 4 (1980) 1–11.
[2] R. B. Bapat, Graphs and matrices, 27, Springer, London; Hindustan Book Agency, New Delhi, 2010.
[3] R. B. Bapat and S. Roy, On the adjacency matrix of a block graph, Linear and Multilinear Algebra, 62 (2014) 406–418.
[4] D. Cartwright and F. Harary, Structural balance: a generalization of Heider’s theory, Psychol Rev., 63 (1956) 277–293.
[5] J. Ding and A. Zhou, Eigenvalues of rank-one updated matrices with some applications, Appl. Math. Lett., 20 (2007)
1223–1226.
[6] D. Easley and J. Kleinberg, Networks, crowds, and markets, 6, Cambridge Univ Press, 2010.
[7] F. Harary, On the notion of balance of a signed graph, Michigan Math. J., 2 (1953–54) 143–146.
[8] T. Amdeberhan, Determinant of a matrix having diagonal and subdiagonal entries zero, MathOverflow, http://
mathoverflow.net/q/264167, (version: 2017-03-10).
[9] R. Singh, Determinant of a matrix having diagonal and subdiagonal entries zero, MathOverflow, http://mathoverflow.
net/q/264264, (version: 2017-03-10).
[10] R. Singh and R. B. Bapat, Eigenvalues of some signed graphs with negative cliques, arXivpreprintarXiv:1702.06322,
(2017).
[11] R. Singh and R. B. Bapat, On characteristic and permanent polynomials of a matrix, Spec. Matrices, 5 (2017) 97–112.
[12] H. Zhou, The inverse of the distance matrix of a distance well-defined graph, Linear Algebra Appl., 517 (2017) 11–29.
Transactions on Combinatorics
Volume 7, Issue 3 - Serial Number 3
September 2018
Pages 37-54

Files

Cited by

History

  • Receive Date: 11 July 2017
  • Revise Date: 26 November 2017
  • Accept Date: 02 December 2017
  • Published Online: 01 September 2018

Share

How to cite

Statistics