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

Abstract

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.

Keywords

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;

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UM FS - Faculty of Mechanical Engineering
UDC: 519.17
COBISS: 16567385 Link will open in a new window
ISSN: 0012-365X
Views: 41
Downloads: 34
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: Slovenian
Secondary title: Karakterizacija prepovedanih podgrafov nekaterih grafov z uporabo aksiomov vmesnosti
Secondary abstract: 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.
Secondary keywords: matematika;teorija grafov;prepovedani podgrafi;inducirana pot;intervalna funkcija;aksiomi vmesnosti;tetivni grafi;razdaljno dedni grafi;
URN: URN:SI:UM:
Type (COBISS): Not categorized
Pages: str. 951-958
Volume: Vol. 313
Issue: iss. 8
Chronology: 2013
ID: 1476751