✦ LIBER ✦

Proof of a conjecture on irredundance perfect graphs

✍ Scribed by Lutz Volkmann; Vadim E. Zverovich

Publisher: John Wiley and Sons
Year: 2002
Tongue: English
Weight: 157 KB
Volume: 41
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10068

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let ir(G) and γ(G) be the irredundance number and the domination number of a graph G, respectively. A graph G is called irredundance perfect if ir(H)=γ(H), for every induced subgraph H of G. In this article we present a result which immediately implies three known conjectures on irredundance perfect graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 292–306, 2002

📜 SIMILAR VOLUMES

On the strong perfect graph conjecture

✍ Stephan Olariu 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB

A graph G is perfect if for every induced subgraph H of G the chromatic number x(H) equals the largest number w ( H ) of pairwise adjacent vertices in H. Berge's famous Strong Perfect Graph Conjecture asserts that a graph G is perfect if and only if neither G nor its complement C contains an odd cho

Proof of a conjecture on cycles in a bip

Proof of a conjecture on cycles in a bipartite graph

✍ Wang, Hong 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 244 KB 👁 2 views

It was conjectured in [Wang, to appear in The Australasian Journal of Combinatorics] that, for each integer k ≥ 2, there exists . This conjecture is also verified for k = 2, 3 in [Wang, to appear; Wang, manuscript]. In this article, we prove this conjecture to be true if n ≥ 3k, i.e., M (k) ≤ 3k. W

Proof of Mader's conjecture on k-critica

Proof of Mader's conjecture on k-critical n-connected graphs

✍ Su Jianji 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB 👁 1 views

## Abstract Mader conjectured that every __k__‐critical __n__‐connected noncomplete graph __G__ has __2k__ + 2 pairwise disjoint fragments. The author in 9 proved that the conjecture holds if the order of __G__ is greater than (__k__ + 2)__n__. Now we settle this conjecture completely. © 2004 Wiley

Families of graphs complete for the stro

Families of graphs complete for the strong perfect graph Conjecture

✍ D. G. Corneil 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 381 KB 👁 1 views

The Strong Perfect Graph Conjecture states that a graph is perfect iff neither it nor its complement contains an odd chordless cycle of size greater than or equal to 5. In this article it is shown that many families of graphs are complete for this conjecture in the sense that the conjecture is true

Proof of a conjecture on game domination

✍ O. Favaron; H. Karami; R. Khoeilar; S. M. Sheikholeslami; L. Volkmann 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 87 KB 👁 1 views

## Abstract The game domination number of a (simple, undirected) graph is defined by the following game. Two players, \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{A}}$\end{document} and \docume

Solution of fink & straight conjecture o

Solution of fink & straight conjecture on path-perfect complete bipartite graphs

✍ Weiting Cao; Peter Hamburger 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 1 views

## Abstract We consider various edge disjoint partitions of complete bipartite graphs. One case is where we decompose the edge set into edge disjoint paths of increasing lengths. A graph __G__ is __path‐perfect__ if there is a positive integer __n__ such that the edge set __E__(__G__) of the graph