| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva Pomoč

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:URL 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 IG(x,y) interval najkrajših x,y-poti in JG(x,y) interval induciranih x,y-poti v povezanem grafu G. Obravnavani so naslednji trije aksiomi vmesnosti za množico V in R:VtimesVrightarrow2V: (i) xinR(u,y),yinR(x,v),xneqy,|R(u,v)|>2RightarrowxinR(u,v); (ii) xinR(u,v)RightarrowR(u,x)capR(x,v)=x; (iii) xinR(u,y),yinR(x,v),xneqy,RightarrowxinR(u,v). Karakteriziramo razred grafov, za katere IG izpolnjuje (i), razred grafov, za katere JG izpolnjuje (ii) in razred grafov, kjer oba IG in JG izpolnjujeta (iii). Karakterizacije so podane z prepovedanimi induciranimi podgrafi. Izkaže se, da je razred grafov, kjer IG izpolnjuje (i), pravi podrazred razdaljno dednih grafov in da je razred, kjer JG 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 Novo okno
UDK:519.17
COBISS.SI-ID:16567385 Novo okno
ISSN pri članku:0012-365X
NUK URN:URN:SI:UM:DK:JERZMLBH
Datum objave v DKUM:10.07.2015
Število ogledov:1309
Število prenosov:103
Metapodatki:XML DC-XML DC-RDF
Področja:Ostalo
:
CHANGAT, Manoj, LAKSHMIKUTTYAMMA, Anandavally K., MATHEWS, Joseph, PETERIN, Iztok, NARASIMHA-SHENOI, Prasanth G., SEETHAKUTTYAMMA, Geetha in ŠPACAPAN, Simon, 2013, A forbidden subgraph characterization of some graph classes using betweenness axioms. Discrete mathematics [na spletu]. 2013. Vol. 313, no. 8, p. 951–958. [Dostopano 22 januar 2025]. Pridobljeno s: http://dx.doi.org/10.1016/j.disc.2013.01.013
Kopiraj citat
  
Skupna ocena:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:Bookmark and Share


Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:Discrete mathematics
Skrajšan naslov:Discrete math.
Založnik:North-Holland
ISSN:0012-365X
COBISS.SI-ID:1118479 Novo okno

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Karakterizacija prepovedanih podgrafov nekaterih grafov z uporabo aksiomov vmesnosti
Opis:Let IG(x,y) and JG(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:VtimesVrightarrow2V: (i) xinR(u,y),yinR(x,v),xneqy,|R(u,v)|>2RightarrowxinR(u,v); (ii) xinR(u,v)RightarrowR(u,x)capR(x,v)=x; (iii)xinR(u,y),yinR(x,v),xneqy,RightarrowxinR(u,v). We characterize the class of graphs for which IG satisfies (i), and the class for which JG satisfies (ii) and the class for which IG or JG satisfies (iii). The characterization is given by forbidden induced subgraphs. It turns out that the class of graphs for which IG satisfies (i) is a proper subclass of distance hereditary graphs and the class for which JG satisfies (ii) is a proper superclass of distance hereditary graphs. We also give an axiomatic characterization of chordal and Ptolemaic graphs.


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici