Manoj Changat (Avtor), Anandavally K. Lakshmikuttyamma (Avtor), Joseph Mathews (Avtor), Iztok Peterin (Avtor), G. N. Prasanth (Avtor), Geetha Seethakuttyamma (Avtor), Simon Špacapan (Avtor)

Povzetek

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.

Ključne besede

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;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM FS - Fakulteta za strojništvo
UDK: 519.17
COBISS: 16567385 Povezava se bo odprla v novem oknu
ISSN: 0012-365X
Št. ogledov: 41
Št. prenosov: 34
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Slovenski jezik
Sekundarni naslov: Karakterizacija prepovedanih podgrafov nekaterih grafov z uporabo aksiomov vmesnosti
Sekundarni povzetek: 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.
Sekundarne ključne besede: matematika;teorija grafov;prepovedani podgrafi;inducirana pot;intervalna funkcija;aksiomi vmesnosti;tetivni grafi;razdaljno dedni grafi;
URN: URN:SI:UM:
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: str. 951-958
Letnik: Vol. 313
Zvezek: iss. 8
Čas izdaje: 2013
ID: 1476751