A matrix description of weakly bipartitive and bipartitive families. (English) Zbl 1370.05165
Summary: The notions of weakly bipartitive and bipartitive families were introduced by F. de Montgolfier [Décomposition modulaire des graphes: théorie, extensions et algorithmes. Montpellier: Université Montpellier II (PhD Thesis) (2003)] as a general tool for studying some decomposition of graphs and other combinatorial structures. One way to construct such families comes from a result of R. Loewy [Linear Algebra Appl. 78, 23–64 (1986; Zbl 0591.15005)]: Given an irreducible \(n \times n\) matrix \(A\) over a field, the family of partitions \(\{X, Y \}\) of \(\{1, \ldots, n \}\) such that the submatrices \(A [X, Y]\) and \(A [Y, X]\) have a rank at most 1 is weakly bipartitive. In this paper, we show that this family is bipartitive when \(A\) is symmetric. In the converse direction, we prove that weakly bipartitive and bipartitive families are all obtained via the construction above.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C75 | Structural characterization of families of graphs |
| 15A03 | Vector spaces, linear dependence, rank, lineability |
| 15A21 | Canonical forms, reductions, classification |
Citations:
Zbl 0591.15005References:
| [1] | Boussaïri, A.; Chergui, B., Skew-symmetric matrices and their principal minors, Linear Algebra Appl., 485, 47-57 (2015) · Zbl 1323.15004 |
| [2] | Chein, M.; Habib, M.; Maurer, M. C., Partitive hypergraphs, Discrete Math., 37, 35-50 (1981) · Zbl 0478.05071 |
| [3] | Cunningham, W. H., Decomposition of directed graphs, SIAM J. Algebr. Discrete Methods, 3, 214-228 (1982) · Zbl 0497.05031 |
| [4] | Ehrenfeucht, A.; Harju, T.; Rozenberg, G., The Theory of 2-Structures, a Framework for Decomposition and Transformation of Graphs (1999), World Scientific: World Scientific Singapore · Zbl 0981.05002 |
| [5] | Hartfiel, D. J.; Loewy, R., On matrices having equal corresponding principal minors, Linear Algebra Appl., 58, 147-167 (1984) · Zbl 0541.15005 |
| [6] | Gallai, T., Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hung., 18, 25-66 (1967) · Zbl 0153.26002 |
| [7] | Ille, P.; Woodrow, R., Weakly partitive families on infinite sets, Contrib. Discrete Math., 4, 54-80 (2009) · Zbl 1203.05013 |
| [9] | Loewy, R., Principal minors and diagonal similarity of matrices, Linear Algebra Appl., 78, 23-63 (1986) · Zbl 0591.15005 |
| [10] | Maffray, F.; Preissmann, M., A translation of Tibor Gallai’s paper: transitiv orientierbare graphen, (Ramirez-Alfonsin, J. L.; Reed, B. A., Perfect Graphs (2001), Wiley: Wiley New York), 25-66 · Zbl 0989.05050 |
| [11] | de Montgolfier, F., Décomposition modulaire des graphes: Théorie, extensions et algorithmes (2003), Université Montpellier II, PhD thesis |
| [12] | van Lint, J. H.; Seidel, J. J., Equilateral point sets in elliptic geometry, Proc. K. Ned. Akad. Wet., Ser. A, Indag. Math., 69, 335-348 (1966) · Zbl 0138.41702 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
