A characterization of signed graphs with generalized perfect elimination orderings. (English) Zbl 1209.05119
Summary: An important property of chordal graphs is that these graphs are characterized by the existence of perfect elimination orderings on their vertex sets. In this paper, we generalize the notion of perfect elimination orderings to signed graphs, and give a characterization for graphs admitting such orderings, together with characterizations restricted to some subclasses and further properties of those graphs. The definition of our generalized perfect elimination orderings is motivated by a generalization of the classical result that a so-called graphic hyperplane arrangement is free if and only if the corresponding graph is chordal.
MSC:
| 05C22 | Signed and weighted graphs |
Keywords:
signed graph; chordal graph; elimination ordering; characterization; hyperplane arrangementReferences:
| [1] | T. Abe, K. Nuida, Y. Numata, An edge-signed generalization of chordal graphs, free multiplicities on braid arrangements, and their characterizations, in: Proceedings of 21st International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2009, Discrete Math. Theor. Comput. Sci. (in press); T. Abe, K. Nuida, Y. Numata, An edge-signed generalization of chordal graphs, free multiplicities on braid arrangements, and their characterizations, in: Proceedings of 21st International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2009, Discrete Math. Theor. Comput. Sci. (in press) · Zbl 1177.32017 |
| [2] | Abe, T.; Nuida, K.; Numata, Y., Signed-eliminable graphs and free multiplicities on the braid arrangement, J. London Math. Soc. (2), 80, 1, 121-134 (2009) · Zbl 1177.32017 |
| [3] | Athanasiadis, C. A., Deformations of Coxeter hyperplane arrangements and their characteristic polynomials, (Falk, M.; Terao, H., Arrangements-Tokyo 1998. Arrangements-Tokyo 1998, Advanced Studies in Pure Mathematics, vol. 27 (2000), Kinokuniya: Kinokuniya Tokyo), 1-26 · Zbl 0976.32016 |
| [4] | Cordovil, R.; Forge, D.; Klein, S., How is a chordal graph like a supersolvable binary matroid?, Discrete Math., 288, 167-172 (2004) · Zbl 1057.05021 |
| [5] | Diestel, R., (Graph Theory. Graph Theory, Graduate Texts in Mathematics, vol. 173 (2006), Springer-Verlag: Springer-Verlag New York) · Zbl 1086.05001 |
| [6] | Edelman, P. H.; Reiner, V., Free hyperplane arrangements between \(A_{n - 1}\) and \(B_n\), Math. Z., 215, 347-365 (1994) · Zbl 0793.05122 |
| [7] | Fulkerson, D. R.; Gross, O. A., Incidence matrices and interval graphs, Pacific J. Math., 15, 3, 835-855 (1965) · Zbl 0132.21001 |
| [8] | McKee, T. A., Chordally signed graphs, Discrete Appl. Math., 119, 273-280 (2002) · Zbl 1003.05051 |
| [9] | Orlik, P.; Terao, H., Arrangements of Hyperplanes (1992), Springer: Springer New York · Zbl 0757.55001 |
| [10] | Rose, D. J., Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32, 597-609 (1970) · Zbl 0216.02602 |
| [11] | Stanley, R. P., Supersolvable lattices, Algebra Universalis, 2, 197-217 (1972) · Zbl 0256.06002 |
| [12] | Zaslavsky, T., Supersolvable frame-matroid and graphic-lift lattices, Europian J. Combin., 22, 119-133 (2001) · Zbl 0966.05013 |
| [13] | Zaslavsky, T., The geometry of root systems and signed graphs, Am. Math. Mon., 88, 2, 88-105 (1981) · Zbl 0466.05058 |
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.
