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.
A vertex cover $S\subseteq V(G)$ is called a total vertex cover of $G$ if the graph $\langle S \rangle$ induced by set $S$ does not contain isolated vertices, i.e., $ | N_G(v) \cap S | \ge 1$ for every $v \in S$. The total vertex cover number of $G$, denoted by $\beta_t(G)$, is the minimum cardinality of a total vertex...
Aziz B. Tapeing, Sergio R. Canoy· Far East Journal of Mathemat...· 0 citations
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$...
Adam Džavoronok, Ole Gabsdil, Alexander Mylet et al.· 1 citation
For an $n$-vertex graph $G$ and a permutation $\sigma$ of its vertex set, let $\sigma(G)$ denote the corresponding relabelling of $G$, and put $I_G(\sigma)=|E(G)\cap E(\sigma(G))|$. Let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph for which $I_G(\sigma)\geq k$ for every $\sigma$. In his 1977 formulati...
For an $n$-vertex graph $G$ and a permutation $\sigma$ of its vertex set, let $\sigma(G)$ denote the corresponding relabelling of $G$, and put \[ I_G(\sigma)=|E(G)\cap E(\sigma(G))|. \] Let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph for which $I_G(\sigma)\geq k$ for every $\sigma$. In 1977 Erd\H{o}s...
For a graph $\Gamma=(V,E)$ and nonnegative integers $a$ and $b$, a nonempty proper subset $C \subset V$ is called an $(a,b)$-regular set if every vertex in $C$ has exactly $a$ neighbors in $C$, and every vertex in $V\setminus C$ has exactly $b$ neighbors in $C$. In this paper, we study the existence of such sets in con...
A. Abdollahi, J.Bagherian, F. Jafari et al.· 0 citations
A graph $G$ is $k$-vertex-critical if $\chi(G)=k$, but $\chi(H)<k$ for every induced subgraph $H$ of $G$. A graph $G$ is $(H_1,H_2,\dots,H_m)$-free if does not contain $H_i$ as an induced subgraph for any $i\in\{1,2,\dots,m\}$.We provide the following dichotomy that for bipartite graphs $H$ and any fixed integer $k\ge...
Iain Beaton, Ben Cameron· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
