×

Quasi-median graphs and algebras. (English) Zbl 0810.05057

The generalization of median structures yields certain resemblances between nonbipartite graphs and nonsymmetric ternary algebras, and this leads to quasi-median graphs and their algebras. A finite quasi-median graph is a retract of a Cartesian product of complete graphs, where a retraction is an idempotent mapping that preserves or collapses edges, and a quasi-median algebra is a subdirect product of ternary algebras for which the term \((xyz)\) equals \(y\) if \(y= z\) and \(x\) otherwise. Already known results are presented, and the results of the authors are summarized in four theorems which are proved applying numerous notions (they are given in the preliminaries) and operations from graph theory and finitary algebras.
Let \(G= G(V,E)\) be a finite connected graph. In Theorem 1 a list of five conditions is given which are equivalent to the quasi-median property of \(G\). Theorem 2 proves that \(G\) is a quasi-median graph iff every set of vertices that minimizes the total distance to families of vertices (such a set is called median set) is connected and contains no induced \(K_{1,1,2}\). Analogous to Theorem 1 in Theorem 3 statements are given which are equivalent for a finite ternary algebra \(V\). These statements are special axioms for \(V\), and it is shown that \(V\) satisfying several equivalent sets of axioms is associated with a quasi-median graph, for a quasi-median graph with the vertex set \(V\) can be turned into a ternary algebra by a certain given ternary operation. In Theorem 4 it is shown that an intrinsic ternary algebra of \(G\) satisfies at least one of the algebraic identities mentioned in Theorem 3 iff \(G\) is a quasi-median graph.

MSC:

05C75 Structural characterization of families of graphs
08A62 Finitary algebras
05C12 Distance in graphs
05C99 Graph theory
08A40 Operations and polynomials in algebraic structures, primal algebras
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bandelt, Eur. J. Combinat.
[2] Bandelt, Discr. Appl. Math. 8 pp 131– (1984)
[3] and , A Helly theorem in weakly modular space. Preprint. · Zbl 0864.05049
[4] Bandelt, Discr. Math. 45 pp 1– (1983)
[5] Chepoi, Metody Diskretnogo Analiza 49 pp 75– (1989)
[6] d-Convexity and local conditions on graphs. Issledovanija po Prikladnoi Mat. i Inf. Shtiinca, Kishinev (1990) 184–191. · Zbl 0769.05061
[7] , and , Dynamic search in graphs. In: Discrete algorithms and complexity, , , , eds., Academic Press, New York (1987). · Zbl 0643.68083
[8] Chung, Combinatorica 9 pp 111– (1989)
[9] Draškovičová, Math. Slovaca 32 pp 269– (1982)
[10] Connections between some congruence properties in a single algebra. Contributions to General Algebra 3, Hölder-Pichler-Tempsky, Wien (1985) 103–114.
[11] Weak direct product decompositions of algebras The interval function of a graph. Math. Centre Tracts 132, Mathematisch Centrum, Amsterdam (1980).
[12] Dress, Aequationes Math. 34 pp 112– (1987)
[13] Fried, Acta Sci. Math. (Szeged) 41 pp 83– (1979)
[14] Hedlíková, Math. Slovaca 27 pp 249– (1977)
[15] Hedlíková, Czechoslovak Math. J. 33 pp 212– (1983)
[16] Isbell, Trans. Amer. Math. Soc. 260 pp 319– (1980)
[17] Kolibiar, Math Čas. 24 pp 179– (1974)
[18] Mulder, Discrete Math. 24 pp 197– (1978)
[19] The interval function of a graph. Math. Centre Tracts 132, Mathematisch Centrum, Amsterdam (1980).
[20] Nebeský, Čas. Pěst. Mat. 107 pp 116– (1982)
[21] Pixley, Studia Sci. Math. Hung. 19 pp 339– (1984)
[22] Doctoral thesis, Universität Oldenburg (1986).
[23] Wilkeit, Discrete Math. 102 pp 197– (1992)
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.