21 results on '"Xiao, Chuanqi"'
Search Results
2. The maximum number of cliques in graphs with bounded odd circumference
- Author
-
Lv, Zequn, Győri, Ervin, He, Zhen, Salia, Nika, Xiao, Chuanqi, and Zhu, Xiutao
- Subjects
FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) - Abstract
In this work, we give the sharp upper bound for the number of cliques in graphs with bounded odd circumferences. This generalized Tur\'an-type result is an extension of the celebrated Erd\H{o}s and Gallai theorem and a strengthening of Luo's recent result. The same bound for graphs with bounded even circumferences is a trivial application of the theorem of Li and Ning.
- Published
- 2022
- Full Text
- View/download PDF
3. Planar Tur\'an Number of Double Stars
- Author
-
Ghosh, Debarun, Győri, Ervin, Paulos, Addisu, and Xiao, Chuanqi
- Subjects
Mathematics - Combinatorics ,05Cxx - Abstract
Given a graph $F$, the planar Tur\'an number of $F$, denoted $\text{ex}_{\mathcal{P}}(n, F)$, is the maximum number of edges in an $n$-vertex $F$-free planar graph. Such an extremal graph problem was initiated by Dowden while determining sharp upper bound for $\text{ex}_{\mathcal{P}}(n,C_4)$ and $\text{ex}_{\mathcal{P}}(n,C_5)$, where $C_4$ and $C_5$ are cycles of length four and five respectively. In this paper we determined an upper bound for $\text{ex}_{\mathcal{P}}(n,S_{2,2})$, $\text{ex}_{\mathcal{P}}(n,S_{2,3})$, $\text{ex}_{\mathcal{P}}(n,S_{2,4})$, $\text{ex}_{\mathcal{P}}(n,S_{2,5})$, $\text{ex}_{\mathcal{P}}(n,S_{3,3})$ and $\text{ex}_{\mathcal{P}}(n,S_{3,4})$, where $S_{m,n}$ is a double star with $m$ and $n$ leafs. Moreover, the bounds for $\text{ex}_{\mathcal{P}}(n,S_{2,2})$ and $\text{ex}_{\mathcal{P}}(n,S_{2,3})$ are sharp.
- Published
- 2021
4. Generalized outerplanar Tur\'an number of short paths
- Author
-
Győri, Ervin, Paulos, Addisu, and Xiao, Chuanqi
- Subjects
Mathematics::Combinatorics ,Computer Science::Discrete Mathematics ,Mathematics - Combinatorics ,Computer Science::Data Structures and Algorithms - Abstract
Let $H$ be a graph. The generalized outerplanar Tur\'an number of $H$, denoted by $f_{\mathcal{OP}}(n,H)$, is the maximum number of copies of $H$ in an $n$-vertex outerplanar graph. Let $P_k$ be the path on $k$ vertices. In this paper we give an exact value of $f_{\mathcal{OP}}(n,P_4)$ and a best asymptotic value of $f_{\mathcal{OP}}(n,P_5)$. Moreover, we characterize all outerplanar graphs containing $f_{\mathcal{OP}}(n,P_4)$ copies of $P_4$., Comment: 23 pages, 12 figures
- Published
- 2021
5. The Tur\'an Number of the Triangular Pyramid of $3$-Layers
- Author
-
Ghosh, Debarun, Győri, Ervin, Paulos, Addisu, Xiao, Chuanqi, and Zamora, Oscar
- Subjects
Mathematics - Combinatorics ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) - Abstract
The Tur\'an number of a graph $H$, denoted by $\text{ex}(n, H)$, is the maximum number of edges in an $n$-vertex graph that does not have $H$ as a subgraph. Let $TP_k$ be the triangular pyramid of $k$-layers. In this paper, we determine that $\text{ex}(n,TP_3)= \frac{1}{4}n^2+n+o(n)$ and pose a conjecture for $\text{ex}(n,TP_4)$.
- Published
- 2021
6. Book free $3$-Uniform Hypergraphs
- Author
-
Ghosh, Debarun, Győri, Ervin, Nagy-György, Judit, Paulos, Addisu, Xiao, Chuanqi, and Zamora, Oscar
- Subjects
FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,05Cxx - Abstract
One of the first problems in extremal graph theory was the maximum number of edges that a triangle-free graph can have. Mantel solved this, which built the foundations of what we know as extremal graph theory. The natural progression was to ask the maximum number of edges in a $k$-book free graph. A $k$-book, denoted by $B_k$, is $k$ triangles sharing a common edge. In the early 2000s, Gy\H{o}ri \cite{gyori1} solved the hypergraph analog of the maximum number of hyperedges in a triangle-free hypergraph. In a hypergraph, $k$-book denotes $k$ Berge triangles sharing a common edge. Let $\text{ex}_3(n,\mathcal{F})$ denote the maximum number of hyperedges in a Berge-$\mathcal{F}$-free hypergraph on $n$ vertices. In this paper, we prove $\text{ex}_3(n,B_k)=\frac{n^2}{8}(1+o(1))$.
- Published
- 2021
- Full Text
- View/download PDF
7. The Tur��n Number of the Triangular Pyramid of $3$-Layers
- Author
-
Ghosh, Debarun, Gy��ri, Ervin, Paulos, Addisu, Xiao, Chuanqi, and Zamora, Oscar
- Subjects
FOS: Mathematics ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,Combinatorics (math.CO) - Abstract
The Tur��n number of a graph $H$, denoted by $\text{ex}(n, H)$, is the maximum number of edges in an $n$-vertex graph that does not have $H$ as a subgraph. Let $TP_k$ be the triangular pyramid of $k$-layers. In this paper, we determine that $\text{ex}(n,TP_3)= \frac{1}{4}n^2+n+o(n)$ and pose a conjecture for $\text{ex}(n,TP_4)$.
- Published
- 2021
- Full Text
- View/download PDF
8. Planar Tur��n Number of Double Stars
- Author
-
Ghosh, Debarun, Gy��ri, Ervin, Paulos, Addisu, and Xiao, Chuanqi
- Subjects
FOS: Mathematics ,Combinatorics (math.CO) ,05Cxx - Abstract
Given a graph $F$, the planar Tur��n number of $F$, denoted $\text{ex}_{\mathcal{P}}(n, F)$, is the maximum number of edges in an $n$-vertex $F$-free planar graph. Such an extremal graph problem was initiated by Dowden while determining sharp upper bound for $\text{ex}_{\mathcal{P}}(n,C_4)$ and $\text{ex}_{\mathcal{P}}(n,C_5)$, where $C_4$ and $C_5$ are cycles of length four and five respectively. In this paper we determined an upper bound for $\text{ex}_{\mathcal{P}}(n,S_{2,2})$, $\text{ex}_{\mathcal{P}}(n,S_{2,3})$, $\text{ex}_{\mathcal{P}}(n,S_{2,4})$, $\text{ex}_{\mathcal{P}}(n,S_{2,5})$, $\text{ex}_{\mathcal{P}}(n,S_{3,3})$ and $\text{ex}_{\mathcal{P}}(n,S_{3,4})$, where $S_{m,n}$ is a double star with $m$ and $n$ leafs. Moreover, the bounds for $\text{ex}_{\mathcal{P}}(n,S_{2,2})$ and $\text{ex}_{\mathcal{P}}(n,S_{2,3})$ are sharp.
- Published
- 2021
- Full Text
- View/download PDF
9. Tur\'an numbers and anti-Ramsey numbers for short cycles in complete $3$-partite graphs
- Author
-
Fang, Chunqiu, Győri, Ervin, Xiao, Chuanqi, and Xiao, Jimeng
- Subjects
Mathematics - Combinatorics - Abstract
We call a $4$-cycle in $K_{n_{1}, n_{2}, n_{3}}$ multipartite, denoted by $C_{4}^{\text{multi}}$, if it contains at least one vertex in each part of $K_{n_{1}, n_{2}, n_{3}}$. The Tur\'an number $\text{ex}(K_{n_{1},n_{2},n_{3}}, C_{4}^{\text{multi}})$ $\bigg($ respectively, $\text{ex}(K_{n_{1},n_{2},n_{3}},\{C_{3}, C_{4}^{\text{multi}}\})$ $\bigg)$ is the maximum number of edges in a graph $G\subseteq K_{n_{1},n_{2},n_{3}}$ such that $G$ contains no $C_{4}^{\text{multi}}$ $\bigg($ respectively, $G$ contains neither $C_{3}$ nor $C_{4}^{\text{multi}}$ $\bigg)$. We call a $C^{multi}_4$ rainbow if all four edges of it have different colors. The ant-Ramsey number $\text{ar}(K_{n_{1},n_{2},n_{3}}, C_{4}^{\text{multi}})$ is the maximum number of colors in an edge-colored of $K_{n_{1},n_{2},n_{3}}$ with no rainbow $C_{4}^{\text{multi}}$. In this paper, we determine that $\text{ex}(K_{n_{1},n_{2},n_{3}}, C_{4}^{\text{multi}})=n_{1}n_{2}+2n_{3}$ and $\text{ar}(K_{n_{1},n_{2},n_{3}}, C_{4}^{\text{multi}})=\text{ex}(K_{n_{1},n_{2},n_{3}}, \{C_{3}, C_{4}^{\text{multi}}\})+1=n_{1}n_{2}+n_{3}+1,$ where $n_{1}\ge n_{2}\ge n_{3}\ge 1.$
- Published
- 2020
10. A note on the Tur\'an number of disjoint union of wheels
- Author
-
Xiao, Chuanqi and Zamora, Oscar
- Subjects
Mathematics - Combinatorics - Abstract
The Tur\'an number of a graph $H$, $\text{ex}(n,H)$, is the maximum number of edges in a graph on $n$ vertices which does not have $H$ as a subgraph. A wheel $W_n$ is an $n$-vertex graph formed by connecting a single vertex to all vertices of a cycle $C_{n-1}$. Let $mW_{2k+1}$ denote the $m$ vertex-disjoint copies of $W_{2k+1}$. For sufficiently large $n$, we determine the Tur\'an number and all extremal graphs for $mW_{2k+1}$. We also provide the Tur\'an number and all extremal graphs for $W^{h}:=\bigcup\limits^m_{i=1}W_{k_i}$ when $n$ is sufficiently large, where the number of even wheels is $h$ and $h>0$.
- Published
- 2020
11. Planar Tur\'an Number of the $\Theta_6$
- Author
-
Ghosh, Debarun, Győri, Ervin, Paulos, Addisu, Xiao, Chuanqi, and Zamora, Oscar
- Subjects
Mathematics - Combinatorics - Abstract
Let $F$ be a graph. The planar Tur\'an number of $F$, denoted by $\text{ex}_{\mathcal{P}}(n,F)$, is the maximum number of edges in an $n$-vertex planar graph containing no copy of $F$ as a subgraph. Let $\Theta_k$ denote the family of Theta graphs on $k\geq 4$ vertices, that is, a graph obtained by joining a pair of non-consecutive vertices of a $k$-cycle with an edge. Y. Lan, et.al. determined sharp upper bound for $\text{ex}_{\mathcal{P}}(n,\Theta_4)$ and $\text{ex}_{\mathcal{P}}(n,\Theta_5)$. Moreover, they obtained an upper bound for $\text{ex}_{\mathcal{P}}(n,\Theta_6)$. They proved that, $\text{ex}_{\mathcal{P}}(n,\Theta_6)\leq \frac{18}{7}n-\frac{36}{7}$. In this paper, we improve their result by giving a bound which is sharp. In particular, we prove that $\text{ex}_{\mathcal{P}}(n,\Theta_6)\leq \frac{18}{7}n-\frac{48}{7}$ and demonstrate that there are infinitely many $n$ for which there exists a $\Theta_6$-free planar graph $G$ on $n$ vertices, which attains the bound., Comment: 23 pages, 19 figures
- Published
- 2020
12. Planar Tur\'an number of the 6-cycle
- Author
-
Ghosh, Debarun, Győri, Ervin, Martin, Ryan R., Paulos, Addisu, and Xiao, Chuanqi
- Subjects
Mathematics - Combinatorics - Abstract
Let ${\rm ex}_{\mathcal{P}}(n,T,H)$ denote the maximum number of copies of $T$ in an $n$-vertex planar graph which does not contain $H$ as a subgraph. When $T=K_2$, ${\rm ex}_{\mathcal{P}}(n,T,H)$ is the well studied function, the planar Tur\'an number of $H$, denoted by ${\rm ex}_{\mathcal{P}}(n,H)$. The topic of extremal planar graphs was initiated by Dowden (2016). He obtained sharp upper bound for both ${\rm ex}_{\mathcal{P}}(n,C_4)$ and ${\rm ex}_{\mathcal{P}}(n,C_5)$. Later on, Y. Lan, et al. continued this topic and proved that ${\rm ex}_{\mathcal{P}}(n,C_6)\leq \frac{18(n-2)}{7}$. In this paper, we give a sharp upper bound ${\rm ex}_{\mathcal{P}}(n,C_6) \leq \frac{5}{2}n-7$, for all $n\geq 18$, which improves Lan's result. We also pose a conjecture on ${\rm ex}_{\mathcal{P}}(n,C_k)$, for $k\geq 7$., Comment: 27 pages, 17 figures
- Published
- 2020
13. The Maximum Number of Paths of Length Four in a Planar Graph
- Author
-
Ghosh, Debarun, Gy��ri, Ervin, Martin, Ryan R., Paulos, Addisu, Salia, Nika, Xiao, Chuanqi, and Zamora, Oscar
- Subjects
Mathematics::Combinatorics ,Computer Science::Discrete Mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Computer Science::Computational Geometry - Abstract
Let $f(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. The order of magnitude of $f(n,P_k)$, where $P_k$ is a path on $k$ vertices, is $n^{{\lfloor{\frac{k-1}{2}}\rfloor}+1}$. In this paper we determine the asymptotic value of $f(n,P_5)$ and give conjectures for longer paths., 9 pages, 2 figures
- Published
- 2020
14. A note on the Tur��n number of disjoint union of wheels
- Author
-
Xiao, Chuanqi and Zamora, Oscar
- Subjects
FOS: Mathematics ,Combinatorics (math.CO) - Abstract
The Tur��n number of a graph $H$, $\text{ex}(n,H)$, is the maximum number of edges in a graph on $n$ vertices which does not have $H$ as a subgraph. A wheel $W_n$ is an $n$-vertex graph formed by connecting a single vertex to all vertices of a cycle $C_{n-1}$. Let $mW_{2k+1}$ denote the $m$ vertex-disjoint copies of $W_{2k+1}$. For sufficiently large $n$, we determine the Tur��n number and all extremal graphs for $mW_{2k+1}$. We also provide the Tur��n number and all extremal graphs for $W^{h}:=\bigcup\limits^m_{i=1}W_{k_i}$ when $n$ is sufficiently large, where the number of even wheels is $h$ and $h>0$.
- Published
- 2020
- Full Text
- View/download PDF
15. Wiener Index of Quadrangulation Graphs
- Author
-
Győri, Ervin, Paulos, Addisu, and Xiao, Chuanqi
- Subjects
FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) - Abstract
The Wiener index of a graph $G$, denoted $W(G)$, is the sum of the distances between all pairs of vertices in $G$. ��. Czabarka, et al. conjectured that for an $n$-vertex, $n\geq 4$, simple quadrangulation graph $G$, \begin{equation*}W(G)\leq \begin{cases} \frac{1}{12}n^3+\frac{7}{6}n-2, &\text{ $n\equiv 0~(mod \ 2)$,}\\ \frac{1}{12}n^3+\frac{11}{12}n-1, &\text{ $n\equiv 1~(mod \ 2)$}. \end{cases} \end{equation*} In this paper, we confirm this conjecture.
- Published
- 2020
- Full Text
- View/download PDF
16. Tur��n numbers and anti-Ramsey numbers for short cycles in complete $3$-partite graphs
- Author
-
Fang, Chunqiu, Gy��ri, Ervin, Xiao, Chuanqi, and Xiao, Jimeng
- Subjects
FOS: Mathematics ,Combinatorics (math.CO) - Abstract
We call a $4$-cycle in $K_{n_{1}, n_{2}, n_{3}}$ multipartite, denoted by $C_{4}^{\text{multi}}$, if it contains at least one vertex in each part of $K_{n_{1}, n_{2}, n_{3}}$. The Tur��n number $\text{ex}(K_{n_{1},n_{2},n_{3}}, C_{4}^{\text{multi}})$ $\bigg($ respectively, $\text{ex}(K_{n_{1},n_{2},n_{3}},\{C_{3}, C_{4}^{\text{multi}}\})$ $\bigg)$ is the maximum number of edges in a graph $G\subseteq K_{n_{1},n_{2},n_{3}}$ such that $G$ contains no $C_{4}^{\text{multi}}$ $\bigg($ respectively, $G$ contains neither $C_{3}$ nor $C_{4}^{\text{multi}}$ $\bigg)$. We call a $C^{multi}_4$ rainbow if all four edges of it have different colors. The ant-Ramsey number $\text{ar}(K_{n_{1},n_{2},n_{3}}, C_{4}^{\text{multi}})$ is the maximum number of colors in an edge-colored of $K_{n_{1},n_{2},n_{3}}$ with no rainbow $C_{4}^{\text{multi}}$. In this paper, we determine that $\text{ex}(K_{n_{1},n_{2},n_{3}}, C_{4}^{\text{multi}})=n_{1}n_{2}+2n_{3}$ and $\text{ar}(K_{n_{1},n_{2},n_{3}}, C_{4}^{\text{multi}})=\text{ex}(K_{n_{1},n_{2},n_{3}}, \{C_{3}, C_{4}^{\text{multi}}\})+1=n_{1}n_{2}+n_{3}+1,$ where $n_{1}\ge n_{2}\ge n_{3}\ge 1.$
- Published
- 2020
- Full Text
- View/download PDF
17. Planar Tur��n Number of the $��_6$
- Author
-
Ghosh, Debarun, Gy��ri, Ervin, Paulos, Addisu, Xiao, Chuanqi, and Zamora, Oscar
- Subjects
FOS: Mathematics ,Combinatorics (math.CO) - Abstract
Let $F$ be a graph. The planar Tur��n number of $F$, denoted by $\text{ex}_{\mathcal{P}}(n,F)$, is the maximum number of edges in an $n$-vertex planar graph containing no copy of $F$ as a subgraph. Let $��_k$ denote the family of Theta graphs on $k\geq 4$ vertices, that is, a graph obtained by joining a pair of non-consecutive vertices of a $k$-cycle with an edge. Y. Lan, et.al. determined sharp upper bound for $\text{ex}_{\mathcal{P}}(n,��_4)$ and $\text{ex}_{\mathcal{P}}(n,��_5)$. Moreover, they obtained an upper bound for $\text{ex}_{\mathcal{P}}(n,��_6)$. They proved that, $\text{ex}_{\mathcal{P}}(n,��_6)\leq \frac{18}{7}n-\frac{36}{7}$. In this paper, we improve their result by giving a bound which is sharp. In particular, we prove that $\text{ex}_{\mathcal{P}}(n,��_6)\leq \frac{18}{7}n-\frac{48}{7}$ and demonstrate that there are infinitely many $n$ for which there exists a $��_6$-free planar graph $G$ on $n$ vertices, which attains the bound., 23 pages, 19 figures
- Published
- 2020
- Full Text
- View/download PDF
18. Planar Tur��n number of the 6-cycle
- Author
-
Ghosh, Debarun, Gy��ri, Ervin, Martin, Ryan R., Paulos, Addisu, and Xiao, Chuanqi
- Subjects
FOS: Mathematics ,Combinatorics (math.CO) - Abstract
Let ${\rm ex}_{\mathcal{P}}(n,T,H)$ denote the maximum number of copies of $T$ in an $n$-vertex planar graph which does not contain $H$ as a subgraph. When $T=K_2$, ${\rm ex}_{\mathcal{P}}(n,T,H)$ is the well studied function, the planar Tur��n number of $H$, denoted by ${\rm ex}_{\mathcal{P}}(n,H)$. The topic of extremal planar graphs was initiated by Dowden (2016). He obtained sharp upper bound for both ${\rm ex}_{\mathcal{P}}(n,C_4)$ and ${\rm ex}_{\mathcal{P}}(n,C_5)$. Later on, Y. Lan, et al. continued this topic and proved that ${\rm ex}_{\mathcal{P}}(n,C_6)\leq \frac{18(n-2)}{7}$. In this paper, we give a sharp upper bound ${\rm ex}_{\mathcal{P}}(n,C_6) \leq \frac{5}{2}n-7$, for all $n\geq 18$, which improves Lan's result. We also pose a conjecture on ${\rm ex}_{\mathcal{P}}(n,C_k)$, for $k\geq 7$., 27 pages, 17 figures
- Published
- 2020
- Full Text
- View/download PDF
19. The Tur\'an number of the square of a path
- Author
-
Xiao, Chuanqi, Katona, Gyula O. H., Xiao, Jimeng, and Zamora, Oscar
- Subjects
Mathematics::Combinatorics ,Computer Science::Discrete Mathematics ,Mathematics - Combinatorics - Abstract
The Tur\'an number of a graph H, ex(n,H), is the maximum number of edges in a graph on n vertices which does not have H as a subgraph. Let P_k be the path with k vertices, the square P^2_k of P_k is obtained by joining the pairs of vertices with distance one or two in P_k. The powerful theorem of Erd\H{o}s, Stone and Simonovits determines the asymptotic behavior of ex(n,P^2_k). In the present paper, we determine the exact value of ex(n,P^2_5) and ex(n,P^2_6) and pose a conjecture for the exact value of ex(n,P^2_k).
- Published
- 2019
20. The Tur��n number of the square of a path
- Author
-
Xiao, Chuanqi, Katona, Gyula O. H., Xiao, Jimeng, and Zamora, Oscar
- Subjects
Mathematics::Combinatorics ,Computer Science::Discrete Mathematics ,FOS: Mathematics ,Combinatorics (math.CO) - Abstract
The Tur��n number of a graph H, ex(n,H), is the maximum number of edges in a graph on n vertices which does not have H as a subgraph. Let P_k be the path with k vertices, the square P^2_k of P_k is obtained by joining the pairs of vertices with distance one or two in P_k. The powerful theorem of Erd��s, Stone and Simonovits determines the asymptotic behavior of ex(n,P^2_k). In the present paper, we determine the exact value of ex(n,P^2_5) and ex(n,P^2_6) and pose a conjecture for the exact value of ex(n,P^2_k).
- Published
- 2019
- Full Text
- View/download PDF
21. Set systems related to a house allocation problem
- Author
-
Gerbner, Dániel, Keszegh, Balázs, Methuku, Abhishek, Nagy, Dániel T., Patkós, Balázs, Tompkins, Casey, and Xiao, Chuanqi
- Subjects
Computer Science::Computer Science and Game Theory ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) - Abstract
We are given a set $A$ of buyers, a set $B$ of houses, and for each buyer a preference list, i.e., an ordering of the houses. A house allocation is an injective mapping $\tau$ from $A$ to $B$, and $\tau$ is strictly better than another house allocation $\tau'\neq \tau$ if for every buyer $i$, $\tau'(i)$ does not come before $\tau(i)$ in the preference list of $i$. A house allocation is Pareto optimal if there is no strictly better house allocation. Let $s(\tau)$ be the image of $\tau$ (i.e., the set of houses sold in the house allocation $\tau$). We are interested in the largest possible cardinality $f(m)$ of the family of sets $s(\tau)$ for Pareto optimal mappings $\tau$ taken over all sets of preference lists of $m$ buyers. We improve the earlier upper bound on $f(m)$ given by Asinowski, Keszegh and Miltzow by making a connection between this problem and some problems in extremal set theory.
- Published
- 2019
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.