| Naslov: | A forbidden subgraph characterization of some graph classes using betweenness axioms |
|---|
| Avtorji: | ID Changat, Manoj (Avtor)
ID Lakshmikuttyamma, Anandavally K. (Avtor)
ID Mathews, Joseph (Avtor)
ID Peterin, Iztok (Avtor)
ID Narasimha-Shenoi, Prasanth G. (Avtor)
ID Seethakuttyamma, Geetha (Avtor)
ID Špacapan, Simon (Avtor) |
|---|
| Datoteke: |  http://dx.doi.org/10.1016/j.disc.2013.01.013
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Delo ni kategorizirano |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
|
|---|
| Opis: | 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 |
|---|
| Leto izida: | 2013 |
|---|
| Št. strani: | str. 951-958 |
|---|
| Številčenje: | Vol. 313, iss. 8 |
|---|
| PID: | 20.500.12556/DKUM-52009  |
|---|
| UDK: | 519.17 |
|---|
| COBISS.SI-ID: | 16567385 |
|---|
| ISSN pri članku: | 0012-365X |
|---|
| NUK URN: | URN:SI:UM:DK:JERZMLBH |
|---|
| Datum objave v DKUM: | 10.07.2015 |
|---|
| Število ogledov: | 1558 |
|---|
| Število prenosov: | 106 |
|---|
| Metapodatki: |    |
|---|
| Področja: | Ostalo
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
