Search ResultsShowing 1-6 of 6
-
arXiv:2311.04800 (Published 2023-11-08)
The minimum degree of $(K_s, K_t)$-co-critical graphs
Categories: math.COGiven graphs $G, H_1, H_2$, we write $G \rightarrow ({H}_1, H_2)$ if every \{red, blue\}-coloring of the edges of $G$ contains a red copy of $H_1$ or a blue copy of $H_2$. A non-complete graph $G$ is $(H_1, H_2)$-co-critical if $G \nrightarrow ({H}_1, H_2)$ and $G+e\rightarrow ({H}_1, H_2)$ for every edge $e$ in the complement of $G$. The notion of co-critical graphs was initiated by Ne$\check{s}$et$\check{r}$il in 1986. Galluccio, Simonovits and Simonyi in 1992 proved that every $(K_3, K_3)$-co-critical graph on $n\ge6$ vertices has minimum degree at least four, and the bound is sharp for all $n\ge 6$. In this paper, we first extend the aforementioned result to all $(K_s, K_t)$-co-critical graphs by showing that every $(K_s, K_t)$-co-critical graph has minimum degree at least $2t+s-5$, where $t\ge s\ge 3$. We then prove that every $(K_3, K_4)$-co-critical graph on $n\ge9$ vertices has minimum degree at least seven, and the bound is sharp for all $n\ge 9$. This answers a question of the third author in the positive for the case $s=3$ and $t=4$.
-
arXiv:2308.15853 (Published 2023-08-30)
Weak$^*$ degeneracy and weak$^*$ $k$-truncated-degree-degenerate graphs
Comments: 19 pages, 1 figureCategories: math.COThis paper introduces the concept of weak$^*$ degeneracy of a graph that shares many nice properties of degeneracy. We prove that for any $f: V(G) \to \mathbb{N}$, if $G$ is weak$^*$ $f$-degenerate, then $G$ is DP-$f$-paintable and $f$-AT. Hence the weak$^*$ degeneracy of $G$ is an upper bound for many colouring parameters, including the online DP-chromatic number and the Alon-Tarsi number. Let $k$ be a positive integer and let $f(v)=\min\{d_G(v), k\}$ for each vertex $v$ of $G$. If $G$ is weak$^*$ $f$-degenerate (respectively, $f$-choosable), then we say $G$ is weak$^*$ $k$-truncated-degree--degenerate (respectively, $k$-truncated-degree-choosable). Richtor asked whether every 3-connected non-complete planar graph is $6$-truncated-degree-choosable. We construct a 3-connected non-complete planar graph which is not $7$-truncated-degree-choosable, so the answer to Richtor's question is negative even if 6 is replaced by 7. Then we prove that every 3-connected non-complete planar graph is weak$^*$ $16$-truncated-degree-degenerate (and hence $16$-truncated-degree-choosable). For an arbitrary proper minor closed family ${\mathcal G}$ of graphs, let $s$ be the minimum integer such that $K_{s,t} \notin \mathcal{G}$ for some $t$. We prove that there is a constant $k$ such that every $s$-connected non-complete graph $G \in {\mathcal G}$ is weak$^*$ $k$-truncated-degree-degenerate. In particular, for any surface $\Sigma$, there is a constant $k$ such that every 3-connected non-complete graph embeddable on $\Sigma$ is weak$^*$ $k$-truncated-degree-degenerate.
-
arXiv:2104.13898 (Published 2021-04-28)
On the size of $(K_t, K_{1,k})$-co-critical graphs
Comments: arXiv admin note: text overlap with arXiv:1904.07825Categories: math.COGiven graphs $G, H_1, H_2$, we write $G \rightarrow ({H}_1, H_2)$ if every $\{$red, blue$\}$-coloring of the edges of $G$ contains a red copy of $H_1$ or a blue copy of $H_2$. A non-complete graph $G$ is $(H_1, H_2)$-co-critical if $G \nrightarrow ({H}_1, H_2)$, but $G+e\rightarrow ({H}_1, H_2)$ for every edge $e$ in $\overline{G}$. Motivated by a conjecture of Hanson and Toft from 1987, we study the minimum number of edges over all $(K_3, K_{1,k})$-co-critical graphs on $n$ vertices. We prove that for all $t\ge3$ and $k\ge 3$, there exists a constant $\ell(t, k)$ such that, for all $n \ge (t-1)k+1$, if $G$ is a $(K_t, K_{1,k})$-co-critical graph on $n$ vertices, then $$ e(G)\ge \left(2t-4+\frac{k-1}{2}\right)n-\ell(t, k).$$ Furthermore, this linear bound is asymptotically best possible when $t\in\{3, 4,5\}$ and all $k\ge3$ and $n\ge (2t-2)k+1$. It seems non-trivial to construct extremal $(K_t, K_{1,k})$-co-critical graphs for $t\ge6$. We also obtain the sharp bound for the size of $(K_3, K_{1,3})$-co-critical graphs on $n\ge13$ vertices by showing that all such graphs have at least $3n-4$ edges.
-
arXiv:1803.01312 (Published 2018-03-04)
Component edge connectivity of the folded hypercube
Comments: The work was included in the MS thesis of the first author in [On the component connectiviy of hypercubes and folded hypercubes, MS Thesis at Taiyuan University of Technology, 2017]Categories: math.COKeywords: component edge connectivity, folded hypercube, non-complete graph, minimum number, deletion resultsTags: dissertationThe $g$-component edge connectivity $c\lambda_g(G)$ of a non-complete graph $G$ is the minimum number of edges whose deletion results in a graph with at least $g$ components. In this paper, we determine the component edge connectivity of the folded hypercube $c\lambda_{g+1}(FQ_{n})=(n+1)g-(\sum\limits_{i=0}^{s}t_i2^{t_i-1}+\sum\limits_{i=0}^{s} i\cdot 2^{t_i})$ for $g\leq 2^{[\frac{n+1}2]}$ and $n\geq 5$, where $g$ be a positive integer and $g=\sum\limits_{i=0}^{s}2^{t_i}$ be the decomposition of $g$ such that $t_0=[\log_{2}{g}],$ and $t_i=[\log_2({g-\sum\limits_{r=0}^{i-1}2^{t_r}})]$ for $i\geq 1$.
-
arXiv:1503.03272 (Published 2015-03-11)
On the existence of vertex-disjoint subgraphs with high degree sums
Comments: 25 pagesCategories: math.COFor a graph $G$, we denote by $\sigma_{2}(G)$ the minimum degree sum of two non-adjacent vertices if $G$ is non-complete; otherwise, $\sigma_{2}(G) = +\infty$. In this paper, we prove the following two results; (i) If $s_{1}$ and $s_{2}$ are integers with $s_{1}, s_{2} \ge 2$ and if $G$ is a non-complete graph with $\sigma_{2}(G) \ge 2(s_{1} + s_{2} + 1) - 1$, then $G$ contains two vertex-disjoint subgraphs $H_{1}$ and $H_{2}$ such that each $H_{i}$ is a graph of order at least $s_{i}+1$ with $\sigma_{2}(H_{i}) \ge 2s_{i} - 1$. (ii) If $s_{1}$ and $s_{2}$ are integers with $s_{1}, s_{2} \ge 2$ and if $G$ is a non-complete triangle-free graph with $\sigma_{2}(G) \ge 2(s_{1} + s_{2}) - 1$, then $G$ contains two vertex-disjoint subgraphs $H_{1}$ and $H_{2}$ such that each $H_{i}$ is a graph of order at least $2s_{i}$ with $\sigma_{2}(H_{i}) \ge 2s_{i} - 1$. By using this kind of results, we also give some corollaries concerning the degree conditions for vertex-disjoint cycles.
-
arXiv:1110.1268 (Published 2011-10-05)
Note on rainbow connection number of dense graphs
Comments: 4 pagesCategories: math.COAn edge-colored graph $G$ is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. Following an idea of Caro et al., in this paper we also investigate the rainbow connection number of dense graphs. We show that for $k\geq 2$, if $G$ is a non-complete graph of order $n$ with minimum degree $\delta (G)\geq \frac{n}{2}-1+log_{k}{n}$, or minimum degree-sum $\sigma_{2}(G)\geq n-2+2log_{k}{n}$, then $rc(G)\leq k$; if $G$ is a graph of order $n$ with diameter 2 and $\delta (G)\geq 2(1+log_{\frac{k^{2}}{3k-2}}{k})log_{k}{n}$, then $rc(G)\leq k$. We also show that if $G$ is a non-complete bipartite graph of order $n$ and any two vertices in the same vertex class have at least $2log_{\frac{k^{2}}{3k-2}}{k}log_{k}{n}$ common neighbors in the other class, then $rc(G)\leq k$.