𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A partition approach to Vizing's conjecture

✍ Scribed by Chen, Guantao; Piotrowski, Wiktor; Shreve, Warren

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
411 KB
Volume
21
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

In 1963, Vizing [Vichysl. Sistemy 9 (19631, 30-431

conjectured that y ( G X H) 2 y ( G ) y ( H ) , where G X Hdenotes the Cartesian product of graphs, and y(G) is the domination number. In this paper we define the extraction number x(G) and w e prove that

M G ) 5 x(G) 5 y(G), and y ( G x H) 2 x(G)y(H),

where Pz(G) is the 2-packing number of G. Though the equality x(G) = y(G) is proven to hold in several classes of graphs, w e construct an infinite family of graphs which do not satisfy this condition. Also, we show the following lower bound: y ( G X H) 2 y(G)Pz(H) + Pz(G) ( y ( H ) -P,(H)).

📜 SIMILAR VOLUMES

Vizing's conjecture: a survey and recent
Vizing's conjecture: a survey and recent results
✍ Boštjan Brešar,; Paul Dorbec,; Wayne Goddard,; Bert L. Hartnell,; Michael A. Hen 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 380 KB

## Abstract Vizing's conjecture from 1968 asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In this paper we survey the approaches to this central conjecture from domination theory and give some new results alo

A Proof of a Partition Conjecture of Bat
A Proof of a Partition Conjecture of Bateman and Erdős
✍ Jason P Bell 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 97 KB

Bateman and Erdo s found necessary and sufficient conditions on a set A for the kth differences of the partitions of n with parts in A, p (k) A (n), to eventually be positive; moreover, they showed that when these conditions occur p (k+1) A (n) tends to zero as n tends to infinity. Bateman and Erdo

A unified approach to known and unknown
A unified approach to known and unknown cases of Berge's conjecture
✍ Eli Berger; Irith Ben-Arroyo Hartman 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB

## Abstract Berge's elegant dipath partition conjecture from 1982 states that in a dipath partition __P__ of the vertex set of a digraph minimizing , there exists a collection __C__^__k__^ of __k__ disjoint independent sets, where each dipath __P__∈__P__ meets exactly min{|__P__|, __k__} of the ind

On a Conjecture of Nicolas–Sárközy about
On a Conjecture of Nicolas–Sárközy about Partitions
✍ F. Ben saı̈d 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 152 KB

Let N be the set of positive integers, B ¼ fb 1 5 . . . 5b k g & N, N 2 N, and N5b k . For i ¼ 0 or 1, A ¼ A i ðB; NÞ is the set (introduced by Nicolas, Ruzsa, and Sa´rko¨zy, J. Number Theory 73 (1998), 292-317) such that A \ f1; . . . ; Ng ¼ B and pðA; nÞ iðmod2Þ for n 2 N; n4N, where pðA; nÞ denot

A model structure approach to the finiti
A model structure approach to the finitistic dimension conjectures
✍ M. Cortés Izurdiaga; S. Estrada; P. A. Guil Asensio 📂 Article 📅 2012 🏛 John Wiley and Sons 🌐 English ⚖ 222 KB

## Abstract We explore the interlacing between model category structures attained to classes of modules of finite \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathcal {X}$\end{document}‐dimension, for certain classes of modules \documentclass{article}\usepackage{ams