𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximality of the cycle code of a graph

✍ Scribed by Patrick Solé; Thomas Zaslavsky

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
274 KB
Volume
128
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The cycle code of a graph is the binary linear span of the characteristic vectors of circuits. We characterize the graphs whose cycle codes are maximal for the packing problem, based on characterizing the graphs whose girth is at least :(n-c)+ 1 where n and c are the numbers of vertices and connected components.

The cycle code (usually called cycle space) of a graph r is the linear span over F2 of the characteristic vectors of circuits versus edges. The packing properties of these codes have been extensively investigated in the past without achieving much success 5]. To compare well with algebraic codes these codes had, in general, to be augmented [S]. That cycle codes which are maximal codes, in the sense that adding any new code words will reduce the minimum distance d, are very rare can be inferred from the examples in 5] and explains the poor packing properties.

However, the rarity of maximal cycle codes has never been proved. Here we do so by finding them all. It is easiest to do this by first solving the weaker problem of

📜 SIMILAR VOLUMES

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 👁 2 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

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__ ≥

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

Maximal sets of hamilton cycles in compl
Maximal sets of hamilton cycles in complete multipartite graphs
✍ Mike Daven; J. A. MacDougall; C. A. Rodger 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB 👁 2 views

## Abstract A set __S__ of edge‐disjoint hamilton cycles in a graph __G__ is said to be __maximal__ if the edges in the hamilton cycles in __S__ induce a subgraph __H__ of __G__ such that __G__ − __E__(__H__) contains no hamilton cycles. In this context, the spectrum __S__(__G__) of a graph __G__ i

Uniqueness of maximal dominating cycles
Uniqueness of maximal dominating cycles in 3-regular graphs and of hamiltonian cycles in 4-regular graphs
✍ Herbert Fleischner 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 461 KB 👁 2 views

## Abstract We construct 3‐regular (cubic) graphs __G__ that have a dominating cycle __C__ such that no other cycle __C__~1~ of __G__ satisfies __V(C)__ ⊆ __V__(__C__~1~). By a similar construction we obtain loopless 4‐regular graphs having precisely one hamiltonian cycle. The basis for these const