| Title: | A forbidden subgraph characterization of some graph classes using betweenness axioms |
|---|
| Authors: | ID Changat, Manoj (Author)
ID Lakshmikuttyamma, Anandavally K. (Author)
ID Mathews, Joseph (Author)
ID Peterin, Iztok (Author)
ID Narasimha-Shenoi, Prasanth G. (Author)
ID Seethakuttyamma, Geetha (Author)
ID Špacapan, Simon (Author) |
|---|
| Files: |  http://dx.doi.org/10.1016/j.disc.2013.01.013
|
|---|
| Language: | English |
|---|
| Work type: | Not categorized |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FERI - Faculty of Electrical Engineering and Computer Science
|
|---|
| 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 |
|---|
| Year of publishing: | 2013 |
|---|
| Number of pages: | str. 951-958 |
|---|
| Numbering: | Vol. 313, iss. 8 |
|---|
| PID: | 20.500.12556/DKUM-52009  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 0012-365X |
|---|
| COBISS.SI-ID: | 16567385 |
|---|
| NUK URN: | URN:SI:UM:DK:JERZMLBH |
|---|
| Publication date in DKUM: | 10.07.2015 |
|---|
| Views: | 1557 |
|---|
| Downloads: | 106 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
