A forbidden subgraph characterization of some graph classes using betweenness axioms

Changat, Manoj; Lakshmikuttyamma, Anandavally K.; Mathews, Joseph; Peterin, Iztok; Narasimha-Shenoi, Prasanth G.; Seethakuttyamma, Geetha; Špacapan, Simon

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

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:	1309
Downloads:	104
Metadata:
Categories:	Misc.
:	CHANGAT, Manoj, LAKSHMIKUTTYAMMA, Anandavally K., MATHEWS, Joseph, PETERIN, Iztok, NARASIMHA-SHENOI, Prasanth G., SEETHAKUTTYAMMA, Geetha and ŠPACAPAN, Simon, 2013, A forbidden subgraph characterization of some graph classes using betweenness axioms. Discrete mathematics [online]. 2013. Vol. 313, no. 8, p. 951–958. [Accessed 1 April 2025]. Retrieved from: http://dx.doi.org/10.1016/j.disc.2013.01.013 Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Similar works from our repository:

Similar works from other repositories:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:	Discrete mathematics
Shortened title:	Discrete math.
Publisher:	North-Holland
ISSN:	0012-365X
COBISS.SI-ID:	1118479

Secondary language

Language:	English
Title:	Karakterizacija prepovedanih podgrafov nekaterih grafov z uporabo aksiomov vmesnosti
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.

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back