20.500.12556/DKUM-52009 A forbidden subgraph characterization of some graph classes using betweenness axioms Karakterizacija prepovedanih podgrafov nekaterih grafov z uporabo aksiomov vmesnosti Naj bo ▫$I_G(x,y)$▫ interval najkrajših ▫$x,y$▫-poti in ▫$J_G(x,y)$▫ interval induciranih ▫$x,y$▫-poti v povezanem grafu ▫$G$▫. Obravnavani so naslednji trije aksiomi vmesnosti za množico ▫$V$▫ in ▫$R: V times V rightarrow 2^V$▫: (i) ▫$x in R(u,y), y in R(x,v), x neq y, |R(u,v)|>2 Rightarrow x in R(u,v)$▫; (ii) ▫$x in R(u,v) Rightarrow R(u,x) cap R(x,v) = {x}$▫; (iii) ▫$x in R(u,y), y in R(x,v), x neq y, Rightarrow x in R(u,v)$▫. Karakteriziramo razred grafov, za katere ▫$I_G$▫ izpolnjuje (i), razred grafov, za katere ▫$J_G$▫ izpolnjuje (ii) in razred grafov, kjer oba ▫$I_G$▫ in ▫$J_G$▫ izpolnjujeta (iii). Karakterizacije so podane z prepovedanimi induciranimi podgrafi. Izkaže se, da je razred grafov, kjer ▫$I_G$▫ izpolnjuje (i), pravi podrazred razdaljno dednih grafov in da je razred, kjer ▫$J_G$▫ izpolnjuje (ii), pravi nadrazred razdaljno dednih grafov. Podani sta tudi aksiomatični karakterizaciji tetivnih in ptolomejskih grafov. Let ▫$I_G(x,y)$▫ and ▫$J_G(x,y)$▫ be the geodesic and induced path interval between ▫$x$▫ and ▫$y$▫ in a connected graph ▫$G$▫, respectively. The following three betweenness axioms are considered for a set ▫$V$▫ and ▫$R: V times V rightarrow 2^V$▫: (i) ▫$x in R(u,y), y in R(x,v), x neq y, |R(u,v)|>2 Rightarrow x in R(u,v)$▫; (ii) ▫$x in R(u,v) Rightarrow R(u,x) cap R(x,v)= {x}$▫; (iii)▫$x in R(u,y), y in R(x,v), x neq y, Rightarrow x in R(u,v)$▫. We characterize the class of graphs for which ▫$I_G$▫ satisfies (i), and the class for which ▫$J_G$▫ satisfies (ii) and the class for which ▫$I_G$▫ or ▫$J_G$▫ satisfies (iii). The characterization is given by forbidden induced subgraphs. It turns out that the class of graphs for which ▫$I_G$▫ satisfies (i) is a proper subclass of distance hereditary graphs and the class for which ▫$J_G$▫ satisfies (ii) is a proper superclass of distance hereditary graphs. We also give an axiomatic characterization of chordal and Ptolemaic graphs. matematika teorija grafov prepovedani podgrafi inducirana pot intervalna funkcija aksiomi vmesnosti tetivni grafi razdaljno dedni grafi mathematics graph theory forbidden subgraphs induced path interval function betweenness axioms chordal graphs distance hereditary graphs true false false Angleški jezik Angleški jezik Delo ni kategorizirano 2015-07-10 15:32:35 2015-07-10 15:32:35 2022-05-31 03:09:03 2019-07-11 07:34:44 2013 0 0 str. 951-958 iss. 8 Vol. 313 2013 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 1118479 16567385 0012-365X URN:SI:UM:DK:JERZMLBH http://dx.doi.org/10.1016/j.disc.2013.01.013 1 https://dk.um.si/Dokument.php?lang=slv&id=76569 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0