Search

Given two graphs $G_1$ and $G_2$, the Ramsey number $r(G_1,G_2)$ refers to the smallest positive integer $N$ such that any graph $G$ with $N$ vertices contains $G_1$ as a subgraph, or the complement of $G$ contains $G_2$ as a subgraph. A connected graph $H$ is said to be $p$-good if $r(K_p,H)=(p-1)(|H|-1)+1$. A generalized fan, denoted as $K_1+nH$, is formed by the disjoint union of $n$ copies of $H$ along with an additional vertex that is connected to each vertex of $nH$. Recently Chung and Lin proved that $K_1+nH$ is $p$-good for $n\ge cp\ell/|H|$, where $c\approx 52.456$ and $\ell=r(K_{p},H)$. They also posed the question of improving the lower bound of $n$ further so that $K_1+nH$ remains $p$-good. In this paper, we present three different methods to improve the range of $n$. First, we apply the Andr\'asfai-Erd\H{o}s-S\'os theorem to reduce $c$ from $52.456$ to $3$. Second, we utilize the approach established by Chen and Zhang to achieve a further reduction of $c$ to $2$. Lastly, we employ a new method to bring $c$ down to $1$. In addition, when $K_1+nH$ forms a fan graph $F_n$, we can further obtain a slightly more refined bound of $n$.

The generalized Tur\'an number $\ex(n,K_s,F)$ denotes the maximum number of copies of $K_s$ in an $n$-vertex $F$-free graph. Let $kF$ denote $k$ disjoint copies of $F$. Gerbner, Methuku and Vizer [DM, 2019, 3130-3141] gave a lower bound for $\ex(n,K_3,2C_5)$ and obtained the magnitude of $\ex(n, K_s, kK_r)$. In this paper, we determine the exact value of $\ex(n,K_3,2C_5)$ and described the unique extremal graph for large $n$. Moreover, we also determine the exact value of $\ex(n,K_r,(k+1)K_r)$ which generalizes some known results.

For a family of graphs $\F$, a graph is called $\F$-free if it does not contain any member of $\F$ as a subgraph. The generalized Tur\'an number $\ex(n,K_r,\F)$ is the maximum number of $K_r$ in an $n$-vertex $\F$-free graph and $\ex(n,K_2,\F)=\ex(n,\F)$, i.e., the classical Tur\'an number. Let $M_{s+1}$ be a matching on $s+1$ edges and $F$ be any graph. In this paper, we determine $\ex(n,K_r, \{M_{s+1},F\})$ apart from a constant additive term and also give a condition when the error constant term can be determined. In particular, we give the exact value of $\ex(n,\{M_{s+1},F\})$ for $F$ being any non-bipartite graph or some bipartite graphs. Furthermore, we determine $\ex(n,K_r,\{M_{s+1},F\})$ when $F$ is color critical with $\chi(F)\ge \max\{r+1,4\}$. These extend the results in [2,11,18].

The Tur\'an number of a graph $F$ is the maximum number of edges in any graph on $n$ vertices containing no $F$ as a subgraph. Let $P_{\ell}$, $S_{\ell-1}$ denote the path and star on $\ell$ vertices, respectively. A linear forest, denoted by $\mathop{\cup}\limits_{i=1}^{k_1} P_{\ell _i}$, is a forest whose connected components are paths. A path-star forest, denoted by $\mathop{\cup}\limits_{i=1}^{k_1} P_{\ell _i} \mathop{\cup}\limits_{j=1}^{k_2} S_{a _j}$, is a forest whose connected components are paths and stars. In 2013, Lidick\'y et al. considered the Tur\'an number of linear forests and path-star forest $k_1P_4 \cup k_2 S_3$ for sufficiently large $n$. In 2021, Yuan and Zhang determined the Tur\'an numbers of the linear forests containing at most one odd path for all $n$ and proposed a conjecture, which is confirmed to be true for $P_{2\ell+1}\cup P_3$, $2P_5$, $3P_5$, $2P_7$ and $2P_9$. Recently, Fang and Yuan determine the Tur\'an numbers and corresponding extremal graphs of $P_{\ell} \cup kS_{\ell-1}$, $2P_5 \cup kS_4$, $k_1P_{2\ell} \cup k_2 S_{2\ell-1}$ for $n$ large enough. In this paper, we determine the Tur\'an numbers of $P_9 \cup P_7$ for all $n\geq 16$ and characterize all extremal graphs, which partially confirms the conjecture proposed by Yuan and Zhang, and determine the Tur\'an numbers and corresponding extremal graphs of $\mathop{\cup}\limits_{i=1}^{k_1} P_{\ell _i} \mathop{\cup}\limits_{j=1}^{k_2} S_{a _j}$ for $n$ large enough, which generalizes the results of Fang and Yuan.

Let $G$ be a graph with $n$ vertices. The {\em hat guessing number} of $G$ is defined in terms of the following game: There are $n$ players and one opponent. The opponent will wear one of the $q$ hats of different colors on the player's head. At this time, the player can only see the player's hat color at the adjacent vertex, and communication between players is not allowed. Once players are assigned hats, each player must guess the color of his hat at the same time. If at least one player guesses right, then they will win collectively. Given a graph $G$, its hat guessing number $HG(G)$ is the largest integer $q$ such that there exists a guessing strategy guaranteeing at least one correct guess for any hat assignment of $q$ different colors. Let $\mathcal{G}(n,p)$ denote the Erd\H{o}s-R\'{e}nyi random graphs with $n$ vertices and edge-chosen probability $ p\in(0,1)$. Alon-Chizewer and Bosek-Dudek-Farnik-Grytczuk-Mazur investigated the lower and upper bound for $HG(G)$ when $G\in \mathcal{G}(n,1/2)$, respectively. In this paper, we extends their results by showing that for any constant number $p$, we have $n^{1 - o(1)}\le HG(G) \le (1-o(1))n$ with high probability when $G\in \mathcal{G}(n,p)$.

Let $X$ and $Y$ be any two graphs of order $n$. The friends-and-strangers graph $\mathsf{FS}(X,Y)$ of $X$ and $Y$ is a graph with vertex set consisting of all bijections $\sigma :V(X) \mapsto V(Y)$, in which two bijections $\sigma$, $\sigma'$ are adjacent if and only if they differ precisely on two adjacent vertices of $X$, and the corresponding mappings are adjacent in $Y$. The most fundamental question that one can ask about these friends-and-strangers graphs is whether or not they are connected. Let $K_{k,n-k}$ be a complete bipartite graph of order $n$. In 1974, Wilson characterized the connectedness of $\mathsf{FS}(K_{1,n-1},Y)$ by using algebraic methods. In this paper, by using combinatorial methods, we investigate the connectedness of $\mathsf{FS}(K_{k,n-k},Y)$ for any $Y$ and all $k\ge 2$, including $Y$ being a random graph, as suggested by Defant and Kravitz, and pose some open problems.

Let $X$ and $Y$ be any two graphs of order $n$. The friends-and-strangers graph $\mathsf{FS}(X,Y)$ of $X$ and $Y$ is a graph with vertex set consisting of all bijections $\sigma :V(X) \mapsto V(Y)$, in which two bijections $\sigma$, $\sigma'$ are adjacent if and only if they differ precisely on two adjacent vertices of $X$, and the corresponding mappings are adjacent in $Y$. The most fundamental question that one can ask about these friends-and-strangers graphs is whether or not they are connected. Let $\mathsf{Lollipop}_{n-k,k}$ be a lollipop graph of order $n$ obtained by identifying one end of a path of order $n-k+1$ with a vertex of a complete graph of order $k$. Defant and Kravitz started to study the connectedness of $\mathsf{FS}(\mathsf{Lollipop}_{n-k,k},Y)$. In this paper, we give a sufficient and necessary condition for $\mathsf{FS}(\mathsf{Lollipop}_{n-k,k},Y)$ to be connected for all $2\leq k\leq n$.

Consider two graphs $X$ and $Y$, each with $n$ vertices. The friends-and-strangers graph $\mathsf{FS}(X,Y)$ of $X$ and $Y$ is a graph with vertex set consisting of all bijections $\sigma :V(X) \mapsto V(Y)$, where two bijections $\sigma$, $\sigma'$ are adjacent if and only if they differ precisely on two adjacent vertices of $X$, and the corresponding mappings are adjacent in $Y$. The most fundamental question that one can ask about these friends-and-strangers graphs is whether or not they are connected. Alon, Defant, and Kravitz showed that if $X$ and $Y$ are two independent random graphs in $\mathcal{G}(n,p)$, then the threshold probability guaranteeing the connectedness of $\mathsf{FS}(X,Y)$ is $p_0=n^{-1/2+o(1)}$, and suggested to investigate the general asymmetric situation, that is, $X\in \mathcal{G}(n,p_1)$ and $Y\in \mathcal{G}(n,p_2)$. In this paper, we show that if $p_1 p_2 \ge p_0^2=n^{-1+o(1)}$ and $p_1, p_2 \ge w(n) p_0$, where $w(n)\rightarrow 0$ as $n\rightarrow \infty$, then $\mathsf{FS}(X,Y)$ is connected with high probability, which extends the result on $p_1=p_2=p$, due to Alon, Defant, and Kravitz., Comment: 16 pages, 1 fighres. This is a version revised mainly under very careful comments from the anonymous referees. arXiv admin note: substantial text overlap with arXiv:2009.07840 by other authors

The Tur\'an number $ex(n,H)$ is the maximum number of edges in an $H$-free graph on $n$ vertices. Let $T$ be any tree. The odd-ballooning of $T$, denoted by $T_o$, is a graph obtained by replacing each edge of $T$ with an odd cycle containing the edge, and all new vertices of the odd cycles are distinct. In this paper, we determine the exact value of $ex(n,T_o)$ for sufficiently large $n$ and $T_o$ being good, which generalizes all the known results on $ex(n,T_o)$ for $T$ being a star, due to Erd\H{o}s et al. (1995), Hou et al. (2018) and Yuan (2018), and provides some counterexamples with chromatic number 3 to a conjecture of Keevash and Sudakov (2004), on the maximum number of edges not in any monochromatic copy of $H$ in a $2$-edge-coloring of a complete graph of order $n$.

The generalized Tur\'{a}n number $ex(n,K_s,H)$ is the maximum number of complete graph $K_s$ in an $H$-free graph on $n$ vertices. Let $F_k$ be the friendship graph consisting of $k$ triangles. Erd\H{o}s and S\'os (1976) determined the value of $ex(n,K_3,F_2)$. Alon and Shikhelman (2016) proved that $ex(n,K_3, F_k)\le (9k-15)(k+1)n.$ In this paper, by using a method developed by Chung and Frankl in hypergraph theory, we determine the exact value of $ex(n,K_3,F_k)$ and the extremal graph for any $F_k$ when $n\ge 4k^3$.

The generalized Tur\'{a}n number $ex(n,K_s,H)$ is defined to be the maximum number of copies of a complete graph $K_s$ in any $H$-free graph on $n$ vertices. Let $F$ be a linear forest consisting of $k$ paths of orders $\ell_1,\ell_2,...,\ell_k$. In this paper, by characterizing the structure of the $F$-free graph with large minimum degree, we determine the value of $ex(n,K_s,F)$ for $n=\Omega\left(|F|^s\right)$ and $k\geq 2$ except some $\ell_i=3$, and the corresponding extremal graphs. The special case when $s=2$ of our result improves some results of Bushaw and Kettle (2011) and Lidick\'{y} et al. (2013) on the classical Tur\'{a}n number for linear forests.

For a graph $H$ and an integer $k\ge1$, the $k$-color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $m\ge4$ vertices and let $\Theta_m$ denote the family of graphs obtained from $C_m$ by adding an additional edge joining two non-consecutive vertices. Unlike Ramsey number of odd cycles, little is known about the general behavior of $R_k(C_{2n})$ except that $R_k(C_{2n})\ge (n-1)k+n+k-1$ for all $k\ge2$ and $n\ge2$. In this paper, we study Ramsey number of even cycles with chords under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. For an integer $k\geq 1$, the Gallai-Ramsey number $GR_k(H)$ of a graph $H$ is the least positive integer $N$ such that every Gallai $k$-coloring of the complete graph $K_N$ contains a monochromatic copy of $H$. We prove that $GR_k(\Theta_{2n})=(n-1)k+n+1$ for all $k\geq 2$ and $n\geq 3$. This implies that $GR_k(C_{2n})=(n-1)k+n+1$ all $k\geq 2$ and $n\geq 3$. Our result yields a unified proof for the Gallai-Ramsey number of all even cycles on at least four vertices., Comment: arXiv admin note: text overlap with arXiv:1809.00227

Elastic Optical Network (EON) has been considered as a promising optical networking technology to architect the next-generation backbone networks. Routing and Spectrum Assignment (RSA) is the fundamental problem in EONs to realize service provisioning. Generally, the RSA is solved by routing the requests with lightpaths first and then assigning spectrum resources to the lightpaths to optimize the spectrum usage. Thus, the spectrum assignment explicitly decide the final spectrum usage of EONs. However, besides the spectrum assignment, there are three other factors, the network topology, traffic distribution and routing scheme, implicitly impact on the spectrum usage. Few related work involves in the implicit impact mechanism. In this paper, we aim to provide a thoroughly theoretical analysis on the impact of the three key factors on the spectrum usage. To this end, two theoretical chains are proposed: (1) The optimal spectrum usage can be measured by the chromatic number of the conflict graph, which is positively correlated to the intersecting probability, \emph{i.e.}, the smaller the intersecting probability, the smaller the optimal spectrum usage; (2) The intersecting probability is decided by the network topology, traffic distribution and routing scheme via a quadratic programming parameterized with a matrix of conflict coefficients. The effectiveness of our theoretical analysis has been validated by extensive numerical results. Meanwhile, our theoretical deductions also permit to give several constant approximation ratios for RSA algorithms.

Network virtualization provides a promising solution to overcome the ossification of current networks, allowing multiple Virtual Network Requests (VNRs) embedded on a common infrastructure. The major challenge in network virtualization is the Virtual Network Embedding (VNE) problem, which is to embed VNRs onto a shared substrate network and known to be $\mathcal{NP}$-hard. The topological heterogeneity of VNRs is one important factor hampering the performance of the VNE. However, in many specialized applications and infrastructures, VNRs are of some common structural features $\textit{e.g.}$, paths and cycles. To achieve better outcomes, it is thus critical to design dedicated algorithms for these applications and infrastructures by taking into accounting topological characteristics. Besides, paths and cycles are two of the most fundamental topologies that all network structures consist of. Exploiting the characteristics of path and cycle embeddings is vital to tackle the general VNE problem. In this paper, we investigated the path and cycle embedding problems. For path embedding, we proved its $\mathcal{NP}$-hardness and inapproximability. Then, by utilizing Multiple Knapsack Problem (MKP) and Multi-Dimensional Knapsack Problem (MDKP), we proposed an efficient and effective MKP-MDKP-based algorithm. For cycle embedding, we proposed a Weighted Directed Auxiliary Graph (WDAG) to develop a polynomial-time algorithm to determine the least-resource-consuming embedding. Numerical results showed our customized algorithms can boost the acceptance ratio and revenue compared to generic embedding algorithms in the literature.

A Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai $k$-coloring is a Gallai coloring that uses at most $k$ colors. For an integer $k\geq 1$, the Gallai-Ramsey number $GR_k(H)$ of a given graph $H$ is the least positive integer $N$ such that every Gallai $k$-coloring of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $m\ge4$ vertices and let $\Theta_m$ denote the family of graphs obtained from $C_m$ by adding an additional edge joining two non-consecutive vertices. We prove that $GR_k(\Theta_{2n+1})=n\cdot 2^k+1$ for all $k\geq 1$ and $n\geq 3$. This implies that $GR_k(C_{2n+1})=n\cdot 2^k+1$ all $k\geq 1$ and $n\geq 3$. Our result yields a unified proof for the Gallai-Ramsey number of all odd cycles on at least five vertices.