𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A tight bound on the length of odd cycles in the incompatibility graph of a non-C1P matrix

✍ Scribed by Mehrnoush Malekesmaeili; Cedric Chauve; Tamon Stephen

Book ID
116577146
Publisher
Elsevier Science
Year
2012
Tongue
English
Weight
296 KB
Volume
112
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A tight lower bound on the maximum genus
A tight lower bound on the maximum genus of a simplicial graph
✍ Jianer Chen; Saroja P. Kanchi; Jonathan L. Gross πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 856 KB

It is proved that every connected simplicial graph with minimum valence at least three has maximum genus at least one-quarter of its cycle rank. This follows from the technical result that every 3-regular simplicial graph except K4 has a Xuong co-tree whose odd components have only one edge each. It

On the number of cycles of length k in a
On the number of cycles of length k in a maximal planar graph
✍ S. L. Hakimi; E. F. Schmeichel πŸ“‚ Article πŸ“… 1979 πŸ› John Wiley and Sons 🌐 English βš– 723 KB

Let G be a maximal planar graph with p vertices, and let Ck(G) denote the number of cycles of length k in G. We first present tight bounds for C,(G) and C,(G) in terms of p. We then give bounds for Ck(G) when 5 5 k 5 p , and consider in particular bounds for C,(G), in terms of p. Some conjectures an

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 πŸ‘ 2 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__ β‰₯