Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
all-paths convexity; transit function; block graph
all-paths convexity; transit function; block graph
Summary:
A transit function $R$ on a set $V$ is a function $R\:V\times V\rightarrow 2^{V}$ satisfying the axioms $u\in R(u,v)$, $R(u,v)=R(v,u)$ and $R(u,u)=\lbrace u\rbrace $, for all $u,v \in V$. The all-paths transit function of a connected graph is characterized by transit axioms.
References:
[1] P. Duchet: Convexity in combinatorial structures. Rend. Circ. Mat. Palermo (2) Suppl. 14 (1987), 261–293. MR 0920860 | Zbl 0644.52001
[2] P. Duchet: Convex sets in graphs II. Minimal path convexity. J. Combin. Theory Ser. B 44 (1988), 307–316. DOI 10.1016/0095-8956(88)90039-1 | MR 0941439 | Zbl 0672.52001
[3] J. Calder: Some elementary properties of interval convexities. J. London Math. Soc. 3 (1971), 422–428. DOI 10.1112/jlms/s2-3.3.422 | MR 0288664 | Zbl 0228.52001
[4] M. Farber and R. E. Jamison: Convexity in graphs and hypergraphs. SIAM J. Algebraic Discrete Methods 7 (1986), 433–444. DOI 10.1137/0607049 | MR 0844046
[5] S. Klavžar and H. M. Mulder: Median graphs: characterizations, location theory and related structures. J. Combin. Math. Combin. Comput. 30 (1999), 103–127. MR 1705337
[6] H. M. Mulder: The Interval Function of a Graph. Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980. MR 0605838 | Zbl 0446.05039
[7] H. M. Mulder: Transit functions on graphs. In preparation. Zbl 1166.05019
[8] M. A. Morgana and H. M. Mulder: The induced path convexity, betweenness, and svelte graphs. Discrete Math (to appear). MR 1910118
[9] L. Nebeský: A characterization of the interval function of a connected graph. Czechoslovak Math. J. 44(119) (1994), 173–178. MR 1257943
[10] L. Nebeský: Characterizing the interval function of a connected graph. Math. Bohem. 123(2) (1998), 137–144. MR 1673965
[11] E. Sampathkumar: Convex sets in graphs. Indian J. Pure Appl. Math. 15 (1984), 1065–1071. MR 0765010
[12] M. L. J. van de Vel: Theory of Convex Structures. North Holland, Amsterdam, 1993. MR 1234493
Search
Partner of
