A dominating set in a graph $G$ is a subset $S$ of its vertices such that each vertex in $G$ is either in $S$ or adjacent to a vertex in $S$. Nordhaus-Gaddum inequalities relate the values of a graph parameter on a graph and its complement. In this setting, Keough and Shane conjecture that any graph $G$ on $n$ vertices satisfies $\partial(G) + \partial(\bar{G}) \leq 2(2^{\lfloor n/2 \rfloor} - 1)(2^{\lceil n/2 \rceil} - 1) + 2$, where $\partial(G)$ is the number of dominating sets in $G$. We partially resolve this conjecture for the bipartite case by proving the stronger bound: for a bipartite graph $G$ with nonempty bipartition $(A,B)$, it holds that $\partial(G) + \partial(\bar{G}) \leq 2(2^{|A|} - 1)(2^{|B|} - 1) + 2$. We also characterize the bipartite graphs for which equality holds.
A graph $\Gamma$ is $(c,t)$-sparse for $c>0$ and $t \ge 1$ if for every pair of vertex subsets $A, B \subseteq V(\Gamma)$ with $|A|, |B| \ge t$, the number of edges $e(A,B)$ between them satisfies $ e(A,B) \le (1 - c)|A||B|$. In this paper, we prove that for every integer $\ell\ge2$, there are $\varepsilon>0, C, C'>0$ such that if an $n$-vertex graph $\Gamma$ is $(1-\varepsilon,t)$-sparse for some $t$, and has at least $Ct^{1-1/\ell}n^{1+1/\ell}$ edges, then $\Gamma$ contains at least $C'n^2t^{2\ell-2}$ induced copies of $C_{2\ell}$. This partially resolves a problem of Ding, Gao, Liu, Luan, and Sun.
Adam Džavoronok, Ole Gabsdil, Alexander Mylet et al.· 1 citation
A path in a properly edge-colored graph is rainbow if its edges have pairwise distinct colors. For a proper edge-coloring $c$ of a graph $G$, let $\operatorname{rpc}(G,c)$ be the minimum number of rainbow paths needed to cover $E(G)$, and let $\operatorname{rpc}(G)$ be the maximum of $\operatorname{rpc}(G,c)$ over all proper edge-colorings of $G$. We prove that, for every fixed $0<\alpha<1$, every properly edge-colored $n$-vertex graph with minimum degree at least $\alpha n$ satisfies $\operatorname{rpc}(G,c)\leq(1+o(1))n/2$, where the coefficient $1/2$ is best possible. We also determine $\operatorname{rpc}(G)$ asymptotically for every complete multipartite graph. If $G=K_{n_1,\ldots,n_r}$ has order $n$ and largest and smallest part sizes $M$ and $s$, respectively, then, uniformly over all choices of the number and sizes of the parts, $\operatorname{rpc}(G)=(1+o(1))\max\{\min\{\lfloor n/2\rfloor,n-M\},(n-s)/2\}$. The proof combines pseudorandom packings of globally rainbow linear forests with a decomposition into dense parts and prescribed avoidance for arbitrary dense graphs, and with reserved connectors and a direct dominant-part argument for complete multipartite graphs.
Let $G = (V(G), E(G))$ be a nontrivial connected graph. A subset $S\subseteq V(G)$ is called an outer-connected weakly connected 2-dominating set in $G$ if every vertex $v \in V(G)\setminus S$ is adjacent to at least two vertices in $S$, the subgraph $\langle S \rangle_w$ weakly induced by $S$ is connected, and the induced subgraph $\langle V(G)\setminus S \rangle$ is connected. The minimum cardinality of such a set, denoted by $\gamma_{oc2w}(G)$, is called the outer-connected weakly connected 2-domination number of $G$. In this paper, we introduce and establish the general properties of outer-connected weakly connected 2-dominating set. Exact values of the outer-connected weakly connected 2-domination number of $G$ are obtained for some known families of graphs. The outer-connected weakly connected 2-dominating sets in the join of graphs are characterized and their corresponding numbers are obtained. Furthermore, the parameter is investigated under the vertex corona and edge corona of graphs.
Kient Rey L. Zuyco, Mae P. Militante, D. Tejada et al.· Far East Journal of Mathemat...· 0 citations
The total domination number $\gamma_t(G)$ of a graph $G$ is the minimum cardinality of a set $D\subseteq V(G)$ such that every vertex of $G$ has a neighbor in $D$. The annihilation number $a(G)$ is the largest integer $k$ for which the sum of the $k$ smallest degrees of $G$ is at most $|E(G)|$. A well-known conjecture, originating from Graffiti.pc and later formulated explicitly by Desormeaux, Haynes, and Henning, asserts that $\gamma_t(G)\le a(G)+1$ for every connected nontrivial graph $G$. The conjecture is known for graphs of minimum degree at least three and for several classes of graphs having vertices of degree one or two. In this paper we settle the minimum-degree-two case. More precisely, we prove $\gamma_t(G)\le a(G)+1$ for every connected graph $G$ with $\delta(G)=2$. The proof combines two sharp bounds on the total domination number with an estimate for the annihilation number. Moreover, in some specific cases, the stronger inequality $\gamma_t(G)\le a(G)$ holds.
For a graph $G$, let $s^+(G)$ and $s^-(G)$ denote the sums of the squares of its positive and negative adjacency eigenvalues. We determine all equality cases in the conjecture of Elphick, Farber, Goldberg, and Wocjan that every connected graph $G$ on $n$ vertices satisfies \[ \min \{s^+(G),s^-(G)\}\ge n-1. \] Namely, equality for $s^+$ holds exactly for trees, whereas equality for $s^-$ holds exactly for trees and complete graphs. The proof combines the $P_3$-removal lemma in the no-cut-vertex case with a detailed equality analysis of the underlying doubly nonnegative matrix inequality. Every block is forced to be complete, and a minimal-counterexample argument gives an exact rank-one decomposition of the folded matrix $M^c$. The resulting non-edge vanishings, together with $AX=XA$, rule out an interface between a bridge and a nontrivial block.
A graph $G$ is $n$-existentially closed or $n$-e.c. if, for all subsets $S\subseteq V(G)$ with $|S|=n$ and for all partitions $S=A\sqcup B$, there exists a vertex in $V(G)\sm S$ adjacent to all vertices in $A$ and no vertices in $B$. We study the minimum number of edges $m(v,n)$ of a $v$-vertex $n$-e.c. graph, and show that $m(v,2)=3v+O(1)$ while $m(v,n)=\Theta(v\log v)$ for fixed $n\ge 3$. The latter result uses a connection to binary covering arrays. A related parameter is the VC-dimension of $G$, defined as the size of the largest subset of vertices shattered by the neighborhoods of vertices in $G$. We initiate systematic study of the VC-dimensions of strongly regular graphs (SRGs). We characterize the sufficiently large SRGs with VC-dimension 2. Furthermore, we determine the VC-dimension of sufficiently large Latin square graphs and of all SRGs of order at most 28, and we show that the SRGs with a given integer as smallest eigenvalue have bounded VC-dimension.
Isabel T. Byrne, John Byrne, S. Cioabă· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
