Source author record

Aziz Contractor

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

A class of graphs approaching Vizing's conjecture

For any graph $G=(V,E)$ , a subset $S\subseteq V$ \emph{dominates} $G$ if all vertices are contained in the closed neighborhood of $S$ , that is $N[S]=V$ . The minimum cardinality over all such $S$ is called the domination number, written $γ(G)$ . In 1963, V.G. Vizing conjectured that $γ(G \square H) \geq γ(G)γ(H)$ where $\square$ stands for the Cartesian product of graphs. In this note, we define classes of graphs $\mathcal{A}_n$ , for $n\geq 0$ , so that every graph belongs to some such class, and $\mathcal{A}_0$ corresponds to class $A$ of Bartsalkin and German. We prove that for any graph $G$ in class $\mathcal{A}_1$ , $γ(G\square H)\geq \left(γ(G)-\sqrt{γ(G)}\right)γ(H)$ .

preprint2015arXiv

Vizing's Conjecture for Almost All Pairs of Graphs

For any graph $G=(V,E)$ , a subset $S\subseteq V$ $dominates$ $G$ if all vertices are contained in the closed neighborhood of $S$ , that is $N[S]=V$ . The minimum cardinality over all such $S$ is called the domination number, written $γ(G)$ . In 1963, V.G. Vizing conjectured that $γ(G \square H) \geq γ(G)γ(H)$ where $\square$ stands for the Cartesian product of graphs. In this note, we prove that if $\left|G\right|\geq γ(G)γ(H)$ and $\left|H\right|\geq γ(G)γ(H)$ , then the conjecture holds. This result quickly implies Vizing's conjecture for almost all pairs of graphs $G,H$ with $\left|G\right|\geq \left|H\right|$ , satisfying $\left|G\right|\leq q^{\frac{\left|H\right|}{\log_q\left|H\right|}}$ for $q=\frac{1}{1-p}$ and $p$ the edge probability of the Erdős-Rényi random graph.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.