✦ LIBER ✦

A bijection between cliques in graphs and factorizations in free monoids

✍ Scribed by J.-C. Spehner

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 856 KB
Volume: 134
Category: Article
ISSN: 0304-3975
DOI: 10.1016/0304-3975(94)90286-0

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Finding and certifying a large hidden cl

Finding and certifying a large hidden clique in a semirandom graph

✍ Uriel Feige; Robert Krauthgamer 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB

designed an algorithm based on spectral techniques that almost surely finds a clique of size √ n hidden in an otherwise random graph. We show that a different algorithm, based on the Lovász theta function, almost surely both finds the hidden clique and certifies its optimality. Our algorithm has an

Closure, 2-factors, and cycle coverings

Closure, 2-factors, and cycle coverings in claw-free graphs

✍ Ryj�?ek, Zden?k; Saito, Akira; Schelp, R. H. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 239 KB 👁 3 views

In this article, we study cycle coverings and 2-factors of a claw-free graph and those of its closure, which has been defined by the first author (On a closure concept in claw-free graphs, J Combin Theory Ser B 70 (1997), 217-224). For a claw-free graph G and its closure cl(G), we prove: ( 1 (2) G

A new family of distance-regular graphs

A new family of distance-regular graphs and the {0, 1, 2}-cliques in dual polar graphs

✍ Joe Hemmeter; Andries Brouwer 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 743 KB

Stability number and [a,b]-factors in gr

Stability number and [a,b]-factors in graphs

✍ Mekkia Kouider; Zbigniew Lonc 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB

## Abstract A spanning subgraph whose vertices have degrees belonging to the interval [__a,b__], where __a__ and __b__ are positive integers, such that __a__ ≤ __b__, is called an [__a,b__]‐factor. In this paper, we prove sufficient conditions for existence of an [__a,b__]‐factor, a connected [__a,

Regular factors in K1,3-free graphs

✍ S. A. Choudum; M. S. Paulraj 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB 👁 1 views

## Abstract We show that every connected __K__~1,3~‐free graph with minimum degree at least __2k__ contains a __k__‐factor and construct connected __K__~1,3~‐free graphs with minimum degree __k__ + __0__(√__k__) that have no __k__‐factor.

Dilation-free graphs in the l1 metric

✍ J. Cáceres; C.I. Grima; A. Márquez; A. Moreno-González 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 164 KB