BZPEER

preprint2020arXiv

On a Vizing-type integer domination conjecture

Given a simple graph $G$ , a dominating set in $G$ is a set of vertices $S$ such that every vertex not in $S$ has a neighbor in $S$ . Denote the domination number, which is the size of any minimum dominating set of $G$ , by $γ(G)$ . For any integer $k\ge 1$ , a function $f : V (G) \rightarrow \{0, 1, . . ., k\}$ is called a \emph{ $\{k\}$ -dominating function} if the sum of its function values over any closed neighborhood is at least $k$ . The weight of a $\{k\}$ -dominating function is the sum of its values over all the vertices. The $\{k\}$ -domination number of $G$ , $γ_{\{k\}}(G)$ , is defined to be the minimum weight taken over all $\{k\}$ -domination functions. Brešar, Henning, and Klavžar (On integer domination in graphs and Vizing-like problems. \emph{Taiwanese J. Math.} {10(5)} (2006) pp. 1317--1328) asked whether there exists an integer $k\ge 2$ so that $γ_{\{k\}}(G\square H)\ge γ(G)γ(H)$ . In this note we use the Roman $\{2\}$ -domination number, $γ_{R2}$ of Chellali, Haynes, Hedetniemi, and McRae, (Roman $\{2\}$ -domination. \emph{Discrete Applied Mathematics} {204} (2016) pp. 22-28.) to prove that if $G$ is a claw-free graph and $H$ is an arbitrary graph, then $γ_{\{2\}}(G\square H)\ge γ_{R2}(G\square H)\ge γ(G)γ(H)$ , which also implies the conjecture for all $k\ge 2$ .

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)$ .

preprint2016arXiv

Vizing's conjecture for cographs

We show that if $G$ is a cograph, that is $P_4$ -free, then for any graph $H$ , $γ(G\square H)\geq γ(G)γ(H)$ . By the characterization of cographs as a finite sequence of unions and joins of $K_1$ , this result easily follows from that of Bartsalkin and German. However, the techniques used are new and may be useful to prove other results.

preprint2015arXiv

On anti-Ramsey numbers for complete bipartite graphs and the Turan function

Given two graphs $G$ and $H$ with $H\subseteq G$ we consider the anti-Ramsey function $AR(G,H)$ which is the maximum number of colors in any edge-coloring of $G$ so that every copy of $H$ receives the same color on at least one pair of edges. The classical Turán function for a graph $G$ and family of graphs $\mathcal{F}$ , written $ex(G,\mathcal{F})$ , is defined as the maximum number of edges of a subgraph of $G$ not containing any member of $\mathcal{F}$ . We show that there exists a constant $c>0$ so that $AR(K_n,K_{s,t})-ex(K_n,K_{s,t})<cn$ and $c$ depends only on $s$ and $t$ , which implies $AR(K_n,K_{s,t})\leq cn^{2-\frac{1}{s}}$ , for $s\leq t$ by a result of K\H ovari, Sós, and Turán.

preprint2015arXiv

Some work on a problem of Marco Buratti

Marco Buratti's conjecture states that if $p$ is a prime and $L$ a multiset containing $p-1$ non-zero elements from the integers modulo $p$ , then there exists a Hamiltonian path in the complete graph of order $p$ with edge lengths in $L$ . Say that a multiset satisfying the above conjecture is realizable. We generalize the problem for trees, show that multisets can be realized as trees with diameter at least one more than the number of distinct elements in the multiset, and affirm the conjecture for multisets of the form $\{ϕ_k(1)^a, ϕ_k(2)^b, ϕ_k(3)^c\}$ where $ϕ_k(i)=\min\{ki \pmod p, -ki \pmod p\}$ .

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.

preprint2014arXiv

A counterexample to a conjecture of Ghosh

We answer two questions of Shamik Ghosh in the negative. We show that there exists a lobster tree of diameter less than 6 which accepts no alpha-labeling with two central vertices labeled by the critical number and the maximum vertex label. We also show a simple example of a tree of diameter 4, with an even degree central vertex which does not accept a maximum label in any graceful labeling.

preprint2014arXiv

Lobsters with an almost perfect matching are graceful

Let $T$ be a lobster with a matching that covers all but one vertex. We show that in this case, $T$ is graceful.

preprint2014arXiv

On small Mixed Pattern Ramsey numbers

We call the minimum order of any complete graph so that for any coloring of the edges by $k$ colors it is impossible to avoid a monochromatic or rainbow triangle, a Mixed Ramsey number. For any graph $H$ with edges colored from the above set of $k$ colors, if we consider the condition of excluding $H$ in the above definition, we produce a \emph{Mixed Pattern Ramsey number}, denoted $M_k(H)$ . We determine this function in terms of $k$ for all colored $4$ -cycles and all colored $4$ -cliques. We also find bounds for $M_k(H)$ when $H$ is a monochromatic odd cycles, or a star for sufficiently large $k$ . We state several open questions.

preprint2012arXiv

Almost-rainbow edge-colorings of some small subgraphs

Let $f(n,p,q)$ be the minimum number of colors necessary to color the edges of $K_n$ so that every $K_p$ is at least $q$ -colored. We improve current bounds on the {7/4}n-3 $, slightly improving the bound of Axenovich. We make small improvements on bounds of Erd\H os and Gyárfás by showing$ {5/6}n+1\leq f(n,4,5) $and for all even$ n\not\equiv 1 \pmod 3 $,$ f(n,4,5)\leq n-1 $. For a complete bipartite graph$ G=K_{n,n} $, we show an n-color construction to color the edges of$ G $so that every$ C_4\subseteq G$ is colored by at least three colors. This improves the best known upper bound of M. Axenovich, Z. Füredi, and D. Mubayi.

preprint2012arXiv

Appendix for almost-rainbow edge-colorings of some small subgraphs

This appendix for our article, "Almost-rainbow edge-colorings of some small subgraphs", contains the full proof of Theorem 4.1.

preprint2011arXiv

A brief, simple proof of 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 prove the conjecture.

preprint2011arXiv

Nonmedian Direct Products of Graphs with Loops

A \emph{median graph} is a connected graph in which, for every three vertices, there exists a unique vertex $m$ lying on the geodesic between any two of the given vertices. We show that the only median graphs of the direct product $G\times H$ are formed when $G=P_k$ , for any integer $k\geq 3$ and $H=P_l$ , for any integer $l\geq 2$ , with a loop at an end vertex, where the direct product is taken over all connected graphs $G$ on at least three vertices or at least two vertices with at least one loop, and connected graphs $H$ with at least one loop.

preprint2011arXiv

On the Edge-balanced Index Sets of Complete Bipartite Graphs

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$ , and $f$ be a 0-1 labeling of $E(G)$ so that the absolute difference in the number of edges labeled 1 and 0 is no more than one. Call such a labeling $f$ \emph{edge-friendly}. The \emph{edge-balanced index set} of the graph $G$ , $EBI(G)$ , is defined as the absolute difference between the number of vertices incident to more edges labeled 1 and the number of vertices incident to more edges labeled 0 over all edge-friendly labelings $f$ . In 2009, Lee, Kong, and Wang \cite{LeeKongWang} found the $EBI(K_{l,n})$ for $l=1,2,3,4,5$ as well as $l=n$ . We continue the investigation of the $EBI$ of complete bipartite graphs of other orders.

preprint2011arXiv

On the edge-balanced index sets of product graphs

We characterize strongly edge regular product graphs and find the edge-balanced index sets of complete bipartite graphs without a perfect matching, the direct product $K_n\times K_2$ . We also prove a lemma that is helpful to determine the edge-balanced index sets of regular graphs.

preprint2011arXiv

On the number of unlabeled vertices in edge-friendly labelings of graphs

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$ , and $f$ be a 0-1 labeling of $E(G)$ so that the absolute difference in the number of edges labeled 1 and 0 is no more than one. Call such a labeling $f$ \emph{edge-friendly}. We say an edge-friendly labeling induces a \emph{partial vertex labeling} if vertices which are incident to more edges labeled 1 than 0, are labeled 1, and vertices which are incident to more edges labeled 0 than 1, are labeled 0. Vertices that are incident to an equal number of edges of both labels we call \emph{unlabeled}. Call a procedure on a labeled graph a \emph{label switching algorithm} if it consists of pairwise switches of labels. Given an edge-friendly labeling of $K_n$ , we show a label switching algorithm producing an edge-friendly relabeling of $K_n$ such that all the vertices are labeled. We call such a labeling \textit{opinionated}.

Elliot Krop

Research overview

Is this your work?

16 publications

On a Vizing-type integer domination conjecture

A class of graphs approaching Vizing's conjecture

Vizing's conjecture for cographs

On anti-Ramsey numbers for complete bipartite graphs and the Turan function

Some work on a problem of Marco Buratti

Vizing's Conjecture for Almost All Pairs of Graphs

A counterexample to a conjecture of Ghosh

Lobsters with an almost perfect matching are graceful

On small Mixed Pattern Ramsey numbers

Almost-rainbow edge-colorings of some small subgraphs

Appendix for almost-rainbow edge-colorings of some small subgraphs

A brief, simple proof of Vizing's conjecture

Nonmedian Direct Products of Graphs with Loops

On the Edge-balanced Index Sets of Complete Bipartite Graphs

On the edge-balanced index sets of product graphs

On the number of unlabeled vertices in edge-friendly labelings of graphs

See the researcher in context

Building this map preview