✦ LIBER ✦

A characterization of ptolemaic graphs

✍ Scribed by Edward Howorka

Publisher: John Wiley and Sons
Year: 1981
Tongue: English
Weight: 466 KB
Volume: 5
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190050314

No coin nor oath required. For personal study only.

✦ Synopsis

A connected graph G is ptolernaic provided that for each four vertices u,, 1 5 i 5 4, of G, the six distances d, =dG (u,ui), i f j satisfy the inequality d,2d34 5 d,3d24 + d,4d23 (shown by Ptolemy t o hold in Euclidean spaces). Ptolemaic graphs were first investigated by Chartrand and Kay, who showed that weakly geodetic ptolemaic graphs are precisely Husimi trees (in particular, trees are ptolemaic). In the present paper several characterizations of ptolemaic graphs are given. It is shown, for example, that a connected graph G is ptolemaic if and only iffor each nondisjoint cliquesP, Q of G, their intersection is a cutset of G which separates P-Q and 0-P. An operation is exhibited which generates all finite ptolemaic graphs from complete graphs.

📜 SIMILAR VOLUMES

A characterization of Seymour graphs

✍ Ageev, A. A.; Kostochka, A. V.; Szigeti, Z. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 1 views

A connected undirected graph G is called a Seymour graph if the maximum number of edge disjoint T -cuts is equal to the cardinality of a minimum T -join for every even subset T of V (G). Several families of graphs have been shown to be subfamilies of Seymour graphs (Seymour

A characterization of ?-outerplanar grap

A characterization of ?-outerplanar graphs

✍ Wargo, Lawrence 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 528 KB

Chartrand and Harary have shown that if G is a non-outerplanar graph such that, for every edge e, both the deletion G \ e and the contraction G/e of e from G are outerplanar, then G is isomorphic to K4 or K2,3. An a-outerplanar graph is a graph which is not outerplanar such that, for some edge a , b

A characterization of radius-critical gr

A characterization of radius-critical graphs

✍ Siemion Fajtlowicz 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB

A graph G is radius-critical if every proper induced connected subgraph of G has radius strictly smaller than the original graph. Our main purpose is to characterize all such graphs. 1. By a graph we shall mean here a finite, simple, undirected graph. For a connected graph the distance between two

A characterization of partially dual gra

A characterization of partially dual graphs

✍ Iain Moffatt 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 332 KB

In this article, we extend the recently introduced concept of partially dual ribbon graphs to graphs. We then go on to characterize partial duality of graphs in terms of bijections between edge sets of corresponding graphs. This result generalizes a well-known result of J. Edmonds in which natural d

A characterization of domination perfect

A characterization of domination perfect graphs

✍ I. E. Zverovich; V. E. Zverovich 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB

Let u(G) and i(G) be the domination number and independent domination number of a graph G. respectively. Sumner and Moore [8] define a graph G to be domination perfect if y( H) = i( H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization o

A characterization of consistent marked

A characterization of consistent marked graphs

✍ Cornelis Hoede 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 364 KB

## Abstract A marked graph is obtained from a graph by giving each point either a positive or a negative sign. Beineke and Harary raised the problem of characterzing consistent marked graphs in which the product of the signs of the points is positive for every cycle. In this paper a characterizatio