A forbidden subgraph characterization of some graph classes using betweenness axiomsChangat, Manoj (Avtor) Lakshmikuttyamma, Anandavally K. (Avtor) Mathews, Joseph (Avtor) Peterin, Iztok (Avtor) Narasimha-Shenoi, Prasanth G. (Avtor) Seethakuttyamma, Geetha (Avtor) Špacapan, Simon (Avtor) matematikateorija grafovprepovedani podgrafiinducirana potintervalna funkcijaaksiomi vmesnostitetivni grafirazdaljno dedni grafimathematicsgraph theoryforbidden subgraphsinduced pathinterval functionbetweenness axiomschordal graphsdistance hereditary graphsNaj 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.20132015-07-10 15:32:35Delo ni kategorizirano52009UDK: 519.17OceCobissID: 1118479COBISS_ID: 16567385ISSN pri članku: 0012-365XNUK URN: URN:SI:UM:DK:JERZMLBHsl