✦ LIBER ✦

On the connectivity of maximal planar graphs

✍ Scribed by S. L. Hakimi; E. F. Schmeichel

Publisher: John Wiley and Sons
Year: 1978
Tongue: English
Weight: 254 KB
Volume: 2
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190020404

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Maximal chromatic polynomials of connect

Maximal chromatic polynomials of connected planar graphs

✍ Ioan Tomescu 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 429 KB

## Abstract In this paper we obtain chromatic polynomials of connected 3‐ and 4‐chromatic planar graphs that are maximal for positive integer‐valued arguments. We also characterize the class of connected 3‐chromatic graphs having the maximum number of __p__‐colorings for __p__ ≥ 3, thus extending a

On convex embeddings of planar 3-connect

On convex embeddings of planar 3-connected graphs

✍ Kelmans, Alexander 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 2 views

A well-known Tutte's theorem claims that every 3-connected planar graph has a convex embedding into the plane. Tutte's arguments also show that, moreover, for every nonseparating cycle C of a 3-connected graph G, there exists a convex embedding of G such that C is a boundary of the outer face in thi

On the number of hamiltonian cycles in a

On the number of hamiltonian cycles in a maximal planar graph

✍ S. L. Hakimi; E. F. Schmeichel; C. Thomassen 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 243 KB 👁 1 views

## Abstract We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on __p__ vertices. In particular, we construct a __p__‐vertex maximal planar graph containing exactly four Hamiltonian cycles for every __p__ ≥ 12. We also pro

The number of maximal independent sets i

The number of maximal independent sets in connected graphs

✍ Zoltán Füredi 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 286 KB

Generalizing a theorem of Moon and Moser. we determine the maximum number of maximal independent sets in a connected graph on n vertices for n sufficiently large, e.g., n > 50. = I .32. . .). Example 1.2. Let b, = i(C,), where C,z denotes the circuit of length n. Then b, = 3, 6, = 2, b, = 5, and b,

Maximal σ-polynomials of connected 3-chr

Maximal σ-polynomials of connected 3-chromatic graphs

✍ Ioan Tomescu 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 113 KB

## Abstract In the set of graphs of order __n__ and chromatic number __k__ the following partial order relation is defined. One says that a graph __G__ is less than a graph __H__ if __c__~__i__~(__G__) ≤ __c__~__i__~(__H__) holds for every __i__, __k__ ≤ __i__ ≤ __n__ and at least one inequality is

On the number of cycles of length 4 in a

On the number of cycles of length 4 in a maximal planar graph

✍ Ahmad Fawzi Alameddine 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB 👁 1 views

## Abstract Let __p__ and __C__~4~ (__G__) be the number of vertices and the number of 4‐cycles of a maximal planar graph __G__, respectively. Hakimi and Schmeichel characterized those graphs __G__ for which __C__~4~ (__G__) = 1/2(__p__^2^ + 3__p__ ‐ 22). This characterization is correct if __p__ ≥