Xinmin Hou

Search for another author

Author Description

Ask a Question About This Mathematician

The spectral radius of graphs without long cycles

2018-12-27

Jun Gao , Xinmin Hou

View PDF Chat

On the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" display="inline" overflow="scroll"><mml:mrow><mml:mo>{</mml:mo><mml:mi>k</mml:mi><mml:mo>}</mml:mo></mml:mrow></mml:math>-domination number of Cartesian products of graphs

2008-08-20

Xinmin Hou , You Lu

Turán number and decomposition number of intersecting odd cycles

2017-09-13

Xinmin Hou , Yu Qiu , Boyuan Liu

A Note on the Distance-Balanced Property of Generalized Petersen Graphs

2009-11-24

Rui Yang , Xinmin Hou , Ning Li +1 more

A graph $G$ is said to be distance-balanced if for any edge $uv$ of $G$, the number of vertices closer to $u$ than to $v$ is equal to the number … A graph $G$ is said to be distance-balanced if for any edge $uv$ of $G$, the number of vertices closer to $u$ than to $v$ is equal to the number of vertices closer to $v$ than to $u$. Let $GP(n,k)$ be a generalized Petersen graph. Jerebic, Klavžar, and Rall [Distance-balanced graphs, Ann. Comb. 12 (2008) 71–79] conjectured that: For any integer $k\geq 2$, there exists a positive integer $n_0$ such that the $GP(n,k)$ is not distance-balanced for every integer $n\geq n_0$. In this note, we give a proof of this conjecture.

View PDF Chat

On Perfect Matching Coverings and Even Subgraph Coverings

2015-03-04

Xinmin Hou , Hong‐Jian Lai , Cun‐Quan Zhang

A perfect matching covering of a graph G is a set of perfect matchings of G such that every edge of G is contained in at least one member of … A perfect matching covering of a graph G is a set of perfect matchings of G such that every edge of G is contained in at least one member of it. Berge conjectured that every bridgeless cubic graph admits a perfect matching covering of order at most 5 (we call such a collection of perfect matchings a Berge covering of G). A cubic graph G is called a Kotzig graph if G has a 3-edge-coloring such that each pair of colors forms a hamiltonian circuit (introduced by R. Häggkvist, K. Markström, J Combin Theory Ser B 96 (2006), 183–206). In this article, we prove that if there is a vertex w of a cubic graph G such that , the graph obtained from by suppressing all degree two vertices is a Kotzig graph, then G has a Berge covering. We also obtain some results concerning the so-called 5-even subgraph double cover conjecture.

Extremal Graph for Intersecting Odd Cycles

2016-05-13

Xinmin Hou , Yu Qiu , Boyuan Liu

An extremal graph for a graph $H$ on $n$ vertices is a graph on $n$ vertices with maximum number of edges that does not contain $H$ as a subgraph. Let … An extremal graph for a graph $H$ on $n$ vertices is a graph on $n$ vertices with maximum number of edges that does not contain $H$ as a subgraph. Let $T_{n,r}$ be the Turán graph, which is the complete $r$-partite graph on $n$ vertices with part sizes that differ by at most one. The well-known Turán Theorem states that $T_{n,r}$ is the only extremal graph for complete graph $K_{r+1}$. Erdős et al. (1995) determined the extremal graphs for intersecting triangles and Chen et al. (2003) determined the maximum number of edges of the extremal graphs for intersecting cliques. In this paper, we determine the extremal graphs for intersecting odd cycles.

View PDF Chat

The Turán number for the edge blow-up of trees

2021-09-16

Anyao Wang , Xinmin Hou , Boyuan Liu +1 more

An improved probability propagation algorithm for density peak clustering based on natural nearest neighborhood

2022-07-18

Wendi Zuo , Xinmin Hou

View PDF Chat

The spectral radius of graphs without trees of diameter at most four

2019-06-12

Xinmin Hou , Boyuan Liu , Shicheng Wang +2 more

Nikiforov [The spectral radius of graphs without paths and cycles of specified length. Linear Algebra Appl. 2010;432(9):2243–2256] conjectured that for a given integer k, any graph G of sufficiently large … Nikiforov [The spectral radius of graphs without paths and cycles of specified length. Linear Algebra Appl. 2010;432(9):2243–2256] conjectured that for a given integer k, any graph G of sufficiently large order n with spectral radius μ(G)≥μ(Sn,k) contains all trees of order 2k+2, unless G=Sn,k, where Sn,k=Kk∨Kn−k¯ denotes the join of a complete graph of order k and an empty graph of order n−k. In this article, we show that the conjecture is true for trees of diameter at most four, more specifically, we prove that, for k≥2 and n>2(k+2)4, every graph G of order n with μ(G)≥μ(Sn,k) contains all trees T of order 2k+2 and of diameter at most four as a subgraph, unless G=Sn,k.

View PDF Chat

FORWARDING INDICES OF CARTESIAN PRODUCT GRAPHS

2006-09-01

Jun‐Ming Xu , Min Xu , Xinmin Hou

For a given connected graph $G$ of order $n$, a routing $R$ is a set of $n(n-1)$ elementary paths specified for every ordered pair of vertices in $G$. The vertex-forwarding … For a given connected graph $G$ of order $n$, a routing $R$ is a set of $n(n-1)$ elementary paths specified for every ordered pair of vertices in $G$. The vertex-forwarding index $\xi(G)$ (the edge-forwarding index $\pi(G)$) of $G$ is the maximum number of paths of $R$ passing through any vertex (resp. edge) in $G$. In this paper we consider the vertex- and the edge- forwarding indices of the cartesian product of $k$ ($\ge 2$) graphs. As applications of our results, we determine the vertex- and the edge- forwarding indices of some well-known graphs, such as the $n$-dimensional generalized hypercube, the undirected toroidal graph, the directed toroidal graph and the cartesian product of the Petersen graphs.

View PDF Chat

FORWARDING INDICES OF CARTESIAN PRODUCT GRAPHS

2006-01-09

Jun‐Ming Xu , Min Xu , Xinmin Hou

For a given connected graph $G$ of order $n$, a routing $R$ is a set of $n(n-1)$ elementary paths specified for every ordered pair of vertices in $G$. The vertex-forwarding … For a given connected graph $G$ of order $n$, a routing $R$ is a set of $n(n-1)$ elementary paths specified for every ordered pair of vertices in $G$. The vertex-forwarding index $\xi(G)$ (the edge-forwarding index $\pi(G)$) of $G$ is the maximum number of paths of $R$ passing through any vertex (resp. edge) in $G$. In this paper we consider the vertex- and the edge- forwarding indices of the cartesian product of $k\,(\ge 2)$ graphs. As applications of our results, we determine the vertex- and the edge- forwarding indices of some well-known graphs, such as the $n$-dimensional generalized hypercube, the undirected toroidal graph, the directed toroidal graph and the cartesian product of the Petersen graphs.

Odd Induced Subgraphs in Graphs with Treewidth at Most Two

2018-04-19

Xinmin Hou , Lei Yu , Jiaao Li +1 more

View PDF Chat

Minimizing the number of edges in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.svg"><mml:msub><mml:mrow><mml:mi mathvariant="script">C</mml:mi></mml:mrow><mml:mrow><mml:mo>≥</mml:mo><mml:mi>r</mml:mi></mml:mrow></mml:msub></mml:math>-saturated graphs

2021-08-02

Yue Ma , Xinmin Hou , Doudou Hei +1 more

Extremal graph for intersecting odd cycles

2015-01-01

Xinmin Hou , Yu Qiu , Boyuan Liu

An extremal graph for a graph $H$ on $n$ vertices is a graph on $n$ vertices with maximum number of edges that does not contain $H$ as a subgraph. Let … An extremal graph for a graph $H$ on $n$ vertices is a graph on $n$ vertices with maximum number of edges that does not contain $H$ as a subgraph. Let $T_{n,r}$ be the Tur\'{a}n graph, which is the complete $r$-partite graph on $n$ vertices with part sizes that differ by at most one. The well-known Tur\'{a}n Theorem states that $T_{n,r}$ is the only extremal graph for complete graph $K_{r+1}$. Erd\"{o}s et al. (1995) determined the extremal graphs for intersecting triangles and Chen et al. (2003) determined the maximum number of edges of the extremal graphs for intersecting cliques. In this paper, we determine the extremal graphs for intersecting odd cycles.

View PDF Chat

On the Perfect Matchings of Near Regular Graphs

2011-01-04

Xinmin Hou

The total {k}-domatic number of wheels and complete graphs

2010-12-20

Jing Chen , Xinmin Hou , Ning Li

The edge spectrum of $K_4^-$-saturated graphs

2018-01-01

Jun Gao , Xinmin Hou , Yue Ma

Given graphs $G$ and $H$, $G$ is $H$-saturated if $G$ does not contain a copy of $H$ but the addition of any edge $e\notin E(G)$ creates at least one copy … Given graphs $G$ and $H$, $G$ is $H$-saturated if $G$ does not contain a copy of $H$ but the addition of any edge $e\notin E(G)$ creates at least one copy of $H$ within $G$. The edge spectrum of $H$ is the set of all possible sizes of an $H$-saturated graph on $n$ vertices. Let $K_4^-$ be a graph obtained from $K_4$ by deleting an edge. In this note, we show that (a) if $G$ is a $K_4^-$-saturated graph with $|V(G)|=n$ and $|E(G)|>\lfloor \frac{n-1}{2} \rfloor \lceil \frac{n-1}{2} \rceil +2$, then $G$ must be a bipartite graph; (b) there exists a $K_4^-$-saturated non-bipartite graph on $n\ge 10$ vertices with size being in the interval $\left[3n-11, \left\lfloor \frac{n-1}{2} \right\rfloor \left\lceil \frac{n-1}{2} \right\rceil +2\right]$. Together with a result of Fuller and Gould in [{\it On ($\hbox{K}_t-e$)-Saturated Graphs. Graphs Combin., 2018}], we determine the edge spectrum of $K_4^-$ completely, and a conjecture proposed by Fuller and Gould in the same paper also has been resolved.

The Edge Spectrum of $$K_4^-$$ K 4 - -Saturated Graphs

2018-11-01

Jun Gao , Xinmin Hou , Yue Ma

The proof of a conjecture of Bouabdallah and Sotteau

2004-10-19

Min Xu , Xinmin Hou , Jun‐Ming Xu

Abstract Let G be a connected graph of order n . A routing in G is a set of n ( n − 1) fixed paths for all ordered pairs … Abstract Let G be a connected graph of order n . A routing in G is a set of n ( n − 1) fixed paths for all ordered pairs of vertices of G . The edge‐forwarding index of G , π( G ), is the minimum of the maximum number of paths specified by a routing passing through any edge of G taken over all routings in G , and π Δ, n is the minimum of π( G ) taken over all graphs of order n with maximum degree at most Δ. To determine π n −2 p −1, n for 4 p + 2⌈ p /3⌉ + 1 ≤ n ≤ 6 p , A. Bouabdallah and D. Sotteau proposed the following conjecture in [On the edge forwarding index problem for small graphs, Networks 23 (1993), 249–255]. The set 3 × {1, 2, … , ⌈(4 p )/3⌉} can be partitioned into 2 p pairs plus singletons such that the set of differences of the pairs is the set 2 × {1, 2, … , p }. This article gives a proof of this conjecture and determines that π n −2 p −1, n is equal to 5 if 4 p + 2⌈ p /3⌉ + 1 ≤ n ≤ 6 p and to 8 if 3 p + ⌈ p /3⌉ + 1 ≤ n ≤ 3 p + ⌈(3 p )/5⌉ for any p ≥ 2. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 292–296 2004

A note on shortest cycle covers of cubic graphs

2011-11-22

Xinmin Hou , Cun‐Quan Zhang

Abstract Let SCC 3 ( G ) be the length of a shortest 3‐cycle cover of a bridgeless cubic graph G . It is proved in this note that if … Abstract Let SCC 3 ( G ) be the length of a shortest 3‐cycle cover of a bridgeless cubic graph G . It is proved in this note that if G contains no circuit of length 5 (an improvement of Jackson's ( JCTB 1994 ) result: if G has girth at least 7) and if all 5‐circuits of G are disjoint (a new upper bound of SCC 3 ( G ) for the special class of graphs).

Decomposition of Graphs into (k,r)‐Fans and Single Edges

2017-03-21

Xinmin Hou , Yu Qiu , Boyuan Liu

Abstract Let be the largest integer such that, for all graphs G on n vertices, the edge set can be partitioned into at most parts, of which every part either … Abstract Let be the largest integer such that, for all graphs G on n vertices, the edge set can be partitioned into at most parts, of which every part either is a single edge or forms a graph isomorphic to H . Pikhurko and Sousa conjectured that for and all sufficiently large n , where denotes the maximum number of edges of graphs on n vertices that do not contain H as a subgraph. A ‐fan is a graph on vertices consisting of k cliques of order r that intersect in exactly one common vertex. In this article, we verify Pikhurko and Sousa's conjecture for ‐fans. The result also generalizes a result of Liu and Sousa.

View PDF Chat

A Dirac-type theorem for uniform hypergraphs

2020-01-01

Yue Ma , Xinmin Hou , Jun Gao

Dirac (1952) proved that every connected graph of order $n>2k+1$ with minimum degree more than $k$ contains a path of length at least $2k+1$. Erd\H{o}s and Gallai (1959) showed that … Dirac (1952) proved that every connected graph of order $n>2k+1$ with minimum degree more than $k$ contains a path of length at least $2k+1$. Erd\H{o}s and Gallai (1959) showed that every $n$-vertex graph $G$ with average degree more than $k-1$ contains a path of length $k$. The hypergraph extension of the Erd\H{o}s-Gallai Theorem have been given by Gy\H{o}ri, Katona, Lemons~(2016) and Davoodi et al.~(2018). F\"uredi, Kostochka, and Luo (2019) gave a connected version of the Erd\H{o}s-Gallai Theorem for hypergraphs. In this paper, we give a hypergraph extension of the Dirac's Theorem: Given positive integers $n,k$ and $r$, let $H$ be a connected $n$-vertex $r$-graph with no Berge path of length $2k+1$. We show that (1) If $k> r\ge 4$ and $n>2k+1$, then $\delta_1(H)\le\binom{k}{r-1}$. Furthermore, the equality holds if and only if $S'_r(n,k)\subseteq H\subseteq S_r(n,k)$ or $H\cong S(sK_{k+1}^{(r)},1)$; (2) If $k\ge r\ge 2$ and $n>2k(r-1)$, then $\delta_1(H)\le \binom{k}{r-1}$. The result is also a Dirac-type version of the result of F\"uredi, Kostochka, and Luo. As an application of (1), we give a better lower bound of the minimum degree than the ones in the Dirac-type results for Berge Hamiltonian cycle given by Bermond et al.~(1976) and Clemens et al. (2016), respectively.

The size of 3-uniform hypergraphs with given matching number and codegree

2018-11-30

Xinmin Hou , Lei Yu , Jun Gao +1 more

View PDF Chat

Some exact results of the generalized Turán numbers for paths

2023-01-06

Doudou Hei , Xinmin Hou , Boyuan Liu

Spectral extrema of graphs with bounded clique number and matching number

2023-03-31

Hongyu Wang , Xinmin Hou , Yue Ma

View PDF Chat

ON GENERALIZED k-DIAMETER OF k-REGULAR k-CONNECTED GRAPHS

2004-12-01

Xinmin Hou , Tianming Wang

In this paper, motivated by the study of the wide diameter and the Rabin number of graphs, we define the generalized $k$-diameter of $k$-connected graphs, and show that every $k$-regular … In this paper, motivated by the study of the wide diameter and the Rabin number of graphs, we define the generalized $k$-diameter of $k$-connected graphs, and show that every $k$-regular $k$-connected graph on $n$ vertices has the generalized $k$-diameter at most $n/2$ and this upper bound cannot be improved when $n=4k-6+i(2k-4)$.

View PDF Chat

Total domination of Cartesian products of graphs

2007-01-01

Xinmin Hou

Let γ t (G) and γ pr (G) denote the total domination and the paired domination numbers of graph G, respectively, and let G H denote the Cartesian product of … Let γ t (G) and γ pr (G) denote the total domination and the paired domination numbers of graph G, respectively, and let G H denote the Cartesian product of graphs G and H.In this paper, we show that γ t (G)γ t (H) ≤ 5γ t (G H), which improves the known result γ t (G)γ t (H) ≤ 6γ t (G H) given by Henning and Rall.

View PDF Chat

A characterization of (γt,γ2)-trees

2010-01-01

Xinmin Hou , Ning Li , You Lu +1 more

View PDF Chat

Strongly Connected Orientation with Minimum Lexicographic Order of Indegrees

2022-02-01

Hongyu Zhou , Xinmin Hou

Given a simple undirected graph [Formula: see text], an orientation of [Formula: see text] is to assign every edge of [Formula: see text] a direction. Borradaile et al gave a … Given a simple undirected graph [Formula: see text], an orientation of [Formula: see text] is to assign every edge of [Formula: see text] a direction. Borradaile et al gave a greedy algorithm SC-Path-Reversal (in polynomial time) which finds a strongly connected orientation that minimizes the maximum indegree, and conjectured that SC-Path-Reversal is indeed optimal for the ”minimizing the lexicographic order” objective as well. In this note, we give a positive answer to the conjecture, which is that we show that the algorithm SC-PATH-REVERSAL finds a strongly connected orientation that minimizes the lexicographic order of indegrees.

View PDF Chat

Maximal Fractional Cross-Intersecting Families

2023-07-07

Hongkui Wang , Xinmin Hou

View PDF Chat

Parity Subgraphs with Few Common Edges and Nowhere-Zero 5-Flow

2014-08-27

Jiaao Li , Xinmin Hou , Zhen‐Mu Hong +1 more

Decomposition of Graphs into $(k,r)$-Fans and Single Edges

2015-01-01

Xinmin Hou , Yu Qiu , Boyuan Liu

Let $\phi(n,H)$ be the largest integer such that, for all graphs $G$ on $n$ vertices, the edge set $E(G)$ can be partitioned into at most $\phi(n, H)$ parts, of which … Let $\phi(n,H)$ be the largest integer such that, for all graphs $G$ on $n$ vertices, the edge set $E(G)$ can be partitioned into at most $\phi(n, H)$ parts, of which every part either is a single edge or forms a graph isomorphic to $H$. Pikhurko and Sousa conjectured that $\phi(n,H)=\ex(n,H)$ for $\chi(H)\geqs3$ and all sufficiently large $n$, where $\ex(n,H)$ denotes the maximum number of edges of graphs on $n$ vertices that does not contain $H$ as a subgraph. A $(k,r)$-fan is a graph on $(r-1)k+1$ vertices consisting of $k$ cliques of order $r$ which intersect in exactly one common vertex. In this paper, we verify Pikhurko and Sousa's conjecture for $(k,r)$-fans. The result also generalizes a result of Liu and Sousa.

View PDF Chat

Codegree conditions for tilling balanced complete $3$-partite $3$-graphs and generalized 4-cycles

2018-01-01

Xinmin Hou , Boyuan Liu , Yue Ma

Given two $k$-graphs $F$ and $H$, a perfect $F$-tiling (also called an $F$-factor) in $H$ is a set of vertex disjoint copies of $F$ that together cover the vertex set … Given two $k$-graphs $F$ and $H$, a perfect $F$-tiling (also called an $F$-factor) in $H$ is a set of vertex disjoint copies of $F$ that together cover the vertex set of $H$. Let $t_{k-1}(n, F)$ be the smallest integer $t$ such that every $k$-graph $H$ on $n$ vertices with minimum codegree at least $t$ contains a perfect $F$-tiling. Mycroft (JCTA, 2016) determined the asymptotic values of $t_{k-1}(n, F)$ for $k$-partite $k$-graphs $F$. Mycroft also conjectured that the error terms $o(n)$ in $t_{k-1}(n, F)$ can be replaced by a constant that depends only on $F$. In this paper, we improve the error term of Mycroft's result to a sub-linear term when $F=K^3(m)$, the complete $3$-partite $3$-graph with each part of size $m$. We also show that the sub-linear term is tight for $K^3(2)$, {the result also provides another family of counterexamples of Mycroft's conjecture (Gao, Han, Zhao (arXiv, 2016) gave a family of counterexamples when $H$ is a $k$-partite $k$-graph with some restrictions.)} Finally, we show that Mycroft's conjecture holds for generalized 4-cycle $C_4^3$ (the 3-graph on six vertices and four distinct edges $A, B, C, D$ with $A\cup B= C\cup D$ and $A\cap B=C\cap D=\emptyset$), i.e. we determine the exact value of $t_2(n, C_4^3)$.

View PDF Chat

Minimum degree of 3-graphs without long linear paths

2019-01-01

Yue Ma , Xinmin Hou , Jun Gao

A well known theorem in graph theory states that every graph $G$ on $n$ vertices and minimum degree at least $d$ contains a path of length at least $d$, and … A well known theorem in graph theory states that every graph $G$ on $n$ vertices and minimum degree at least $d$ contains a path of length at least $d$, and if $G$ is connected and $n\ge 2d+1$ then $G$ contains a path of length at least $2d$ (Dirac, 1952). In this article, we give an extension of Dirac's result to hypergraphs. We determine asymptotic lower bounds of the minimum degrees of 3-graphs to guarantee linear paths of specific lengths, and the lower bounds are tight up to a constant.

View PDF Chat

H-Decomposition of r-Graphs when H is an r-Graph with Exactly k Independent Edges

2018-11-28

Xinmin Hou , Boyuan Liu , Hongliang Lu

View PDF Chat

Maximizing the number of independent sets of fixed size in $K_n$-covered graphs

2020-01-01

Anyao Wang , Xinmin Hou , Boyuan Liu +1 more

A graph $G$ is $H$-covered by some given graph $H$ if each vertex in $G$ is contained in a copy of $H$. In this note, we give the maximum number … A graph $G$ is $H$-covered by some given graph $H$ if each vertex in $G$ is contained in a copy of $H$. In this note, we give the maximum number of independent sets of size $t\ge 3$ in $K_n$-covered graphs of size $N\ge n+t-1$ and determine its extremal graph. The result answers a question proposed by Chakraborit and Loh. The proof uses an edge-switching operation of hypergraphs which remains the number of independent sets nondecreasing.

View PDF Chat

Minimum degree of 3-graphs without long linear paths

2020-05-19

Yue Ma , Xinmin Hou , Jun Gao

View PDF Chat

The Turán number for the edge blow-up of trees

2020-01-01

Anyao Wang , Xinmin Hou , Boyuan Liu +1 more

The edge blow-up of a graph $F$ is the graph obtained from replacing each edge in $F$ by a clique of the same size where the new vertices of the … The edge blow-up of a graph $F$ is the graph obtained from replacing each edge in $F$ by a clique of the same size where the new vertices of the cliques are all different. In this article, we concern about the Tur\'an problem for the edge blow-up of trees. Erd\H{o}s et al. (1995) and Chen et al. (2003) solved the problem for stars. The problem for paths was resolved by Glebov (2011). Liu (2013) extended the above results to cycles and a special family of trees with the minimum degree at most two in the smaller color class (paths and proper subdivisions of stars were included in the family). In this article, we extend Liu's result to all the trees with the minimum degree at least two in the smaller color class. Combining with Liu's result, except one particular case, the Tur\'an problem for the edge blow-up of trees is completely resolved. Moreover, we determine the maximum number of edges in the family of $\{K_{1,k}, kK_2, 2K_{1,k-1}\}$-free graphs and the extremal graphs, which is an extension of a result given by Abbott et al. (1972).

Exact Minimum Codegree Thresholds for $K_4^-$-Covering and $K_5^-$-Covering

2020-08-07

Lei Yu , Xinmin Hou , Yue Ma +1 more

Given two $3$-graphs $F$ and $H$, an $F$-covering of $H$ is a collection of copies of $F$ in $H$ such that each vertex of $H$ is contained in at least … Given two $3$-graphs $F$ and $H$, an $F$-covering of $H$ is a collection of copies of $F$ in $H$ such that each vertex of $H$ is contained in at least one copy of them. Let $c_2(n,F)$ be the minimum integer $t$ such that every 3-graph with minimum codegree greater than $t$ has an $F$-covering. In this note, we answer an open problem of Falgas-Ravry and Zhao (SIAM J. Discrete Math., 2016) by determining the exact value of $c_2(n, K_4^-)$ and $c_2(n, K_5^-)$, where $K_t^-$ is the complete $3$-graph on $t$ vertices with one edge removed.

View PDF Chat

Rainbow independent sets in graphs with maximum degree two

2022-05-18

Yue Ma , Xinmin Hou , Jun Gao +2 more

View PDF Chat

The Cycle of Length Four is Strictly F-Turán-Good

2023-11-08

Doudou Hei , Xinmin Hou

Long antipaths and anticycles in oriented graphs

2025-01-28

Bin Chen , Xinmin Hou , Xinyu Zhou

View PDF Chat

The spectral radius of graphs without trees of diameter at most four

2016-01-01

Xinmin Hou , Boyuan Liu , Shicheng Wang +2 more

Nikiforov (LAA, 2010) conjectured that for given integer $k$, any graph $G$ of sufficiently large order $n$ with spectral radius $\mu(G)\geq \mu(S_{n,k})$ contains all trees of order $2k+2$, unless $G=S_{n,k}$, … Nikiforov (LAA, 2010) conjectured that for given integer $k$, any graph $G$ of sufficiently large order $n$ with spectral radius $\mu(G)\geq \mu(S_{n,k})$ contains all trees of order $2k+2$, unless $G=S_{n,k}$, where $S_{n,k}=K_k\vee \overline{K_{n-k}}$, the join of a complete graph of order $k$ and an empty graph of order $n-k$. In this paper, we show that the conjecture is true for trees of diameter at most four.

View PDF Chat

Weak Internal Partition of Regular Graphs

2017-07-03

Xinkai Tao , Boyuan Liu , Xinmin Hou

The spectral radius of graphs without long cycles

2017-01-01

Jun Gao , Xinmin Hou

Nikiforov conjectured that for a given integer $k\ge 2$, any graph $G$ of sufficiently large order $n$ with spectral radius $\mu(G)\geq \mu(S_{n,k})$ (or $\mu(G)\ge \mu(S_{n,k}^+))$ contains $C_{2k+1}$ or $C_{2k+2}$(or $C_{2k+2}$), … Nikiforov conjectured that for a given integer $k\ge 2$, any graph $G$ of sufficiently large order $n$ with spectral radius $\mu(G)\geq \mu(S_{n,k})$ (or $\mu(G)\ge \mu(S_{n,k}^+))$ contains $C_{2k+1}$ or $C_{2k+2}$(or $C_{2k+2}$), unless $G=S_{n,k}$ (or $G=S_{n,k}^+)$, where $C_\ell$ is a cycle of length $\ell$ and $S_{n,k}=K_k\vee \overline{K_{n-k}}$, the join graph of a complete graph of order $k$ and an empty graph on $n-k$ vertices, and $S_{n,k}^+$ is the graph obtained from $S_{n,k}$ by adding an edge in the independent set of $S_{n,k}$. %This can be vie as spectral version of Erd\"{o}s and S\'{o}s conjecture. In this paper, a weaker version of Nikiforov's conjecture is considered, we prove that for a given integer $k\ge 2$, any graph $G$ of sufficiently large order $n$ with spectral radius $\mu(G)\geq \mu(S_{n,k})$ (or $\mu(G)\ge \mu(S_{n,k}^+))$ %$C_{2k+1}$ or $C_{2k+2}$(or $C_{2k+2}$), unless $G=S_{n,k}$ (or $G=S_{n,k}^+)$$S_{n,k}$ ( or $S_{n,k}^+$) is the unique extremal graph with maximum radius among all of the graphs of order $n$ and contains a cycle $C_{\ell}$ with $\ell \geq 2k+1$ (or $C_{\ell}$ with $\ell \geq 2k+2$), unless $G=S_{n,k}$ (or $G=S_{n,k}^+)$. These results also imply a result of Nikiforov given in [Theorem 2, The spectral radius of graphs without paths and cycles of specified length, LAA, 2010].

Odd induced subgraphs in graphs with treewidth at most two

2017-01-01

Xinmin Hou , Lei Yu , Jiaao Li +1 more

A long-standing conjecture asserts that there exists a constant $c>0$ such that every graph of order $n$ without isolated vertices contains an induced subgraph of order at least $cn$ with … A long-standing conjecture asserts that there exists a constant $c>0$ such that every graph of order $n$ without isolated vertices contains an induced subgraph of order at least $cn$ with all degrees odd. Scott (1992) proved that every graph $G$ has an induced subgraph of order at least $|V(G)|/(2\chi(G))$ with all degrees odd, where $\chi(G)$ is the chromatic number of $G$, this implies the conjecture for graphs with { bounded} chromatic number. But the factor $1/(2\chi(G))$ seems to be not best possible, for example, Radcliffe and Scott (1995) proved $c=\frac 23$ for trees, Berman, Wang and Wargo (1997) showed that $c=\frac 25$ for graphs with maximum degree $3$, so it is interesting to determine the exact value of $c$ for special family of graphs. In this paper, we further confirm the conjecture for graphs with treewidth at most 2 with $c=\frac{2}{5}$, and the bound is best possible.

The size of $3$-uniform hypergraphs with given matching number and codegree

2017-01-01

Xinmin Hou , Lei Yu , Jun Gao +1 more

Determine the size of $r$-graphs with given graph parameters is an interesting problem. Chv\'atal and Hanson (JCTB, 1976) gave a tight upper bound of the size of 2-graphs with restricted … Determine the size of $r$-graphs with given graph parameters is an interesting problem. Chv\'atal and Hanson (JCTB, 1976) gave a tight upper bound of the size of 2-graphs with restricted maximum degree and matching number; Khare (DM, 2014) studied the same problem for linear $3$-graphs with restricted matching number and maximum degree. In this paper, we give a tight upper bound of the size of $3$-graphs with bounded codegree and matching number.

View PDF Chat

A note on broom number and maximum edge-cut of graphs.

2017-01-01

Zhen‐Mu Hong , Xinmin Hou , Jiaao Li +1 more

$H$-Decomposition of $r$-graphs when $H$ is an $r$-graph with exactly $k$ independent edges

2017-01-01

Xinmin Hou , Boyuan Liu , Hongliang Lu

Let $ϕ_H^r(n)$ be the smallest integer such that, for all $r$-graphs $G$ on $n$ vertices, the edge set $E(G)$ can be partitioned into at most $ϕ_H^r(n)$ parts, of which every … Let $ϕ_H^r(n)$ be the smallest integer such that, for all $r$-graphs $G$ on $n$ vertices, the edge set $E(G)$ can be partitioned into at most $ϕ_H^r(n)$ parts, of which every part either is a single edge or forms an $r$-graph isomorphic to $H$. The function $ϕ^2_H(n)$ has been well studied in literature, but for the case $r\ge 3$, the problem that determining the value of $ϕ_H^r(n)$ is widely open. Sousa (2010) gave an asymptotic value of $ϕ_H^r(n)$ when $H$ is an $r$-graph with exactly 2 edges, and determined the exact value of $ϕ_H^r(n)$ in some special cases. In this paper, we first give the exact value of $ϕ_H^r(n)$ when $H$ is an $r$-graph with exactly 2 edges, which improves Sousa's result. Second we determine the exact value of $ϕ_H^r(n)$ when $H$ is an $r$-graph consisting of exactly $k$ independent edges.

Mod $(2p+1)$-Orientation on Bipartite Graphs and Complementary Graphs

2018-01-01

Jiaao Li , Xinmin Hou , Miaomiao Han +1 more

A mod $(2p+1)$-orientation $D$ is an orientation of $G$ such that $d_D^+(v)-d_D^-(v)\equiv 0 \pmod {2p+1}$ for any vertex $v \in V(G)$. Jaeger conjectured that every $4p$-edge-connected graph has a mod … A mod $(2p+1)$-orientation $D$ is an orientation of $G$ such that $d_D^+(v)-d_D^-(v)\equiv 0 \pmod {2p+1}$ for any vertex $v \in V(G)$. Jaeger conjectured that every $4p$-edge-connected graph has a mod $(2p+1)$-orientation. A graph $G$ is strongly ${\mathbb Z}_{2p+1}$-connected if for every mapping $b: V(G) \mapsto {\mathbb Z}_{2p+1}$ with $\sum_{v\in V(G)}b(v)=0$, there exists an orientation $D$ of $G$ such that $d_D^+(v)-d_D^-(v)= b(v)$ in ${\mathbb Z}_{2p+1}$ for any $v \in V(G)$. A strongly ${\mathbb Z}_{2p+1}$-connected graph admits a mod $(2p+1)$-orientation, and it is a contractible configuration for mod $(2p+1)$-orientation. We prove Jaeger's module orientation conjecture is equivalent to its restriction to bipartite simple graphs and investigate strongly ${\mathbb Z}_{2p+1}$-connectedness of certain bipartite graphs, particularly for $p=2$. We also show that if $G$ is a simple graph with $|V(G)|\ge N(p)= 1152p^4$ and $\min\{\delta(G),\delta(G^c)\}\ge 4p$, then either $G$ or $G^c$ is strongly ${\mathbb Z}_{2p+1}$-connected. When $p=2$, the value of $N(2)$ can be reduced to $N(2) = 80$.

The Degree Threshold for Covering with all the Connected $3$-Graphs with $3$ Edges

2025-02-27

Yue Ma , Xinmin Hou , Zhi Yin

Given two $r$-uniform hypergraphs $F$ and $H$, we say that $H$ has an $F$-covering if every vertex in $H$ is contained in a copy of $F$. Let $c_{i}(n,F)$ be the … Given two $r$-uniform hypergraphs $F$ and $H$, we say that $H$ has an $F$-covering if every vertex in $H$ is contained in a copy of $F$. Let $c_{i}(n,F)$ be the least integer such that every $n$-vertex $r$-graph $H$ with $\delta_{i}(H)>c_i(n,F)$ has an $F$-covering. Falgas-Ravry, Markström and Zhao (Combin. Probab. Comput., 2021) asymptotically determined $c_1(n,K_{4}^{(3)-})$, where $K_{4}^{(3)-}$ is obtained by deleting an edge from the complete $3$-graph on $4$ vertices. Later, Tang, Ma and Hou (Electron. J. Combin., 2023) asymptotically determined $c_1(n,C_{6}^{(3)})$, where $C_{6}^{(3)}$ is the linear triangle, i.e. $C_{6}^{(3)}=([6],\{123,345,561\})$. In this paper, we determine $c_1(n,F_5)$ asymptotically, where $F_5$ is the generalized triangle, i.e. $F_5=([5],\{123,124,345\})$. We also determine the exact values of $c_1(n,F)$, where $F$ is any connected $3$-graph with $3$ edges and $F\notin\{K_4^{(3)-}, C_{6}^{(3)}, F_5\}$.

Long antipaths and anticycles in oriented graphs

2025-01-28

Bin Chen , Xinmin Hou , Xinyu Zhou

View PDF Chat

The maximal sum of sizes of cross intersecting families for multisets

2024-11-05

Hongkui Wang , Xinmin Hou

Let $k$, $t$ and $m$ be positive integers. A $k$-multiset of $[m]$ is a collection of $k$ elements of $[m]$ with repetition and without ordering. We use $\left(\binom {[m]}{k}\right)$ to … Let $k$, $t$ and $m$ be positive integers. A $k$-multiset of $[m]$ is a collection of $k$ elements of $[m]$ with repetition and without ordering. We use $\left(\binom {[m]}{k}\right)$ to denote all the $k$-multisets of $[m]$. Two multiset families $\mathcal{F}$ and $\mathcal{G}$ in $\left(\binom {[m]}{k}\right)$ are called cross $t$-intersecting if $|F\cap G|\geq t$ for any $F\in \mathcal{F}$ and $G\in \mathcal{G}$. Moreover, if $\mathcal{F}=\mathcal{G}$, we call $\mathcal{F}$ a $t$-intersecting family in $\left(\binom {[m]}{k}\right)$. Meagher and Purdy~(2011) presented a multiset variant of Erd\H{o}s-Ko-Rado Theorem for $t$-intersecting family in $\left(\binom {[m]}{k}\right)$ when $t=1$, and F\"uredi, Gerbner and Vizer~(2016) extended this result to general $t\ge 2$ with $m\geq 2k-t$, verified a conjecture proposed by Meagher and Purdy~(2011). In this paper, we determine the maximum sum of cross $t$-intersecting families $\mathcal{F}$ and $\mathcal{G}$ in $\left(\binom {[m]}{k}\right)$ and characterize the extremal families achieving the upper bound. For $t=1$ and $m\geq k+1$, the method involves constructing a bijection between multiset family and set family while preserving the intersecting relation. For $t\ge 2$ and $m\ge 2k-t$, we employ a shifting operation, specifically the down-compression, which was initiated by F\"uredi, Gerbner and Vizer~(2016). These results extend the sum-type intersecting theorem for set families originally given by Hilton and Milner (1967).

View PDF Chat

Faber-Krahn type inequality for supertrees

2024-10-23

Hongyu Wang , Xinmin Hou

The Faber-Krahn inequality states that the first Dirichlet eigenvalue among all bounded domains is no less than a Euclidean ball with the same volume in $\mathbb{R}^n$ \cite{Chavel FB}. B{\i}y{\i}ko\u{g}lu and … The Faber-Krahn inequality states that the first Dirichlet eigenvalue among all bounded domains is no less than a Euclidean ball with the same volume in $\mathbb{R}^n$ \cite{Chavel FB}. B{\i}y{\i}ko\u{g}lu and Leydold (J. Comb. Theory, Ser. B., 2007) demonstrated that the Faber-Krahn inequality also holds for the class of trees with boundary with the same degree sequence and characterized the unique extremal tree. B{\i}y{\i}ko\u{g}lu and Leydold (2007) also posed a question as follows: Give a characterization of all graphs in a given class $\mathcal{C}$ with the Faber-Krahn property. In this paper, we address this question specifically for $k$-uniform supertrees with boundary. We introduce a spiral-like ordering (SLO-ordering) of vertices for supertrees, an extension of the SLO-ordering for trees initially proposed by Pruss [ Duke Math. J., 1998], and prove that the SLO-supertree has the Faber-Krahn property among all supertrees with a given degree sequence. Furthermore, among degree sequences that have a minimum degree $d$ for interior vertices, the SLO-supertree with degree sequence $(d,\ldots,d, d', 1, \dots, 1)$ possesses the Faber-Krahn property.

View PDF Chat

Counting triangles in regular graphs

2024-07-25

Jialin He , Xinmin Hou , Jie Ma +1 more

Abstract In this paper, we investigate the minimum number of triangles, denoted by , in ‐vertex ‐regular graphs, where is an odd integer and is an even integer. The well‐known … Abstract In this paper, we investigate the minimum number of triangles, denoted by , in ‐vertex ‐regular graphs, where is an odd integer and is an even integer. The well‐known Andrásfai–Erdős–Sós Theorem has established that if . In a striking work, Lo has provided the exact value of for sufficiently large , given that . Here, we bridge the gap between the aforementioned results by determining the precise value of in the entire range . This confirms a conjecture of Cambie, de Joannis de Verclos, and Kang for sufficiently large .

View PDF Chat

A Ramsey-type theorem on deficiency

2024-06-03

Jin Sun , Xinmin Hou

Ramsey's Theorem states that a graph $G$ has bounded order if and only if $G$ contains no complete graph $K_n$ or empty graph $E_n$ as its induced subgraph. The Gy\'arf\'as-Sumner … Ramsey's Theorem states that a graph $G$ has bounded order if and only if $G$ contains no complete graph $K_n$ or empty graph $E_n$ as its induced subgraph. The Gy\'arf\'as-Sumner conjecture says that a graph $G$ has bounded chromatic number if and only if it contains no induced subgraph isomorphic to $K_n$ or a tree $T$. The deficiency of a graph is the number of vertices that cannot be covered by a maximum matching. In this paper, we prove a Ramsey type theorem for deficiency, i.e., we characterize all the forbidden induced subgraphs for graphs $G$ with bounded deficiency. As an application, we answer a question proposed by Fujita, Kawarabayashi, Lucchesi, Ota, Plummer and Saito (JCTB, 2006).

View PDF Chat

A Dirac-Type Theorem for Uniform Hypergraphs

2024-06-01

Yue Ma , Xinmin Hou , Jun Gao

On induced subgraph of Cartesian product of paths

2024-05-09

Jiasheng Zeng , Xinmin Hou

Abstract Chung et al. constructed an induced subgraph of the hypercube with vertices and with maximum degree smaller than . Subsequently, Huang proved the Sensitivity Conjecture by demonstrating that the … Abstract Chung et al. constructed an induced subgraph of the hypercube with vertices and with maximum degree smaller than . Subsequently, Huang proved the Sensitivity Conjecture by demonstrating that the maximum degree of such an induced subgraph of hypercube is at least , and posed the question: Given a graph , let be the minimum of the maximum degree of an induced subgraph of on vertices, what can we say about ? In this paper, we investigate this question for Cartesian product of paths , denoted by . We determine the exact values of when by showing that for and , and give a nontrivial lower bound of when by showing that . In particular, when , we have , which is Huang's result. The lower bounds of and are given by using the spectral method provided by Huang.

View PDF Chat

Long antipaths and anticycles in oriented graphs

2024-01-01

Bin Chen , Xinmin Hou , Hongyu Zhou

Let $\delta^{0}(D)$ be the minimum semi-degree of an oriented graph $D$. Jackson (1981) proved that every oriented graph $D$ with $\delta^{0}(D)\geq k$ contains a directed path of length $2k$ when … Let $\delta^{0}(D)$ be the minimum semi-degree of an oriented graph $D$. Jackson (1981) proved that every oriented graph $D$ with $\delta^{0}(D)\geq k$ contains a directed path of length $2k$ when $|V(D)|>2k+2$, and a directed Hamilton cycle when $|V(D)|\le 2k+2$. Stein~(2020) further conjectured that every oriented graph $D$ with $\delta^{0}(D)>k/2$ contains any orientated path of length $k$. Recently, Klimo\u{s}ov\'{a} and Stein (DM, 2023) introduced the minimum pseudo-semi-degree $\tilde\delta^0(D)$ (a slight weaker than the minimum semi-degree condition as $\tilde\delta^0(D)\ge \delta^0(D))$ and showed that every oriented graph $D$ with $\tilde\delta^{0}(D)\ge (3k-2)/4$ contains each antipath of length $k$ for $k\geq 3$. In this paper, we improve the result of Klimo\u{s}ov\'{a} and Stein by showing that for all $k\geq 2$, every oriented graph with $\tilde\delta^0(D)\ge(2k+1)/3$ contains either an antipath of length at least $k+1$ or an anticycle of length at least $k+1$. Furthermore, we answer a problem raised by Klimo\u{s}ov\'{a} and Stein in the negative.

View PDF Chat

The Cycle of Length Four is Strictly F-Turán-Good

2023-11-08

Doudou Hei , Xinmin Hou

The Degree and Codegree Threshold for Linear Triangle Covering in 3-Graphs

2023-11-03

Yuxuan Tang , Yue Ma , Xinmin Hou

Given two $k$-uniform hypergraphs $F$ and $G$, we say that $G$ has an $F$-covering if every vertex in $G$ is contained in a copy of $F$. For $1\le i \le … Given two $k$-uniform hypergraphs $F$ and $G$, we say that $G$ has an $F$-covering if every vertex in $G$ is contained in a copy of $F$. For $1\le i \le k-1$, let $c_i(n,F)$ be the least integer such that every $n$-vertex $k$-uniform hypergraph $G$ with $\delta_i(G)> c_i(n,F)$ has an $F$-covering. The covering problem has been systematically studied by Falgas-Ravry and Zhao [Codegree thresholds for covering 3-uniform hypergraphs, [SIAM J. Discrete Math., 2016]. Last year, Falgas-Ravry, Markström, and Zhao [Triangle-degrees in graphs and tetrahedron coverings in 3-graphs, Combinatorics, Probability and Computing, 2021] asymptotically determined $c_1(n, F)$ when $F$ is the generalized triangle. In this note, we give the exact value of $c_2(n, F)$ and asymptotically determine $c_1(n, F)$ when $F$ is the linear triangle $C_6^3$, where $C_6^3$ is the 3-uniform hypergraph with vertex set $\{v_1,v_2,v_3,v_4,v_5,v_6\}$ and edge set $\{v_1v_2v_3,v_3v_4v_5,v_5v_6v_1\}$.

View PDF Chat

Maximal Fractional Cross-Intersecting Families

2023-07-07

Hongkui Wang , Xinmin Hou

View PDF Chat

Spectral extrema of graphs with bounded clique number and matching number

2023-03-31

Hongyu Wang , Xinmin Hou , Yue Ma

View PDF Chat

Some exact results of the generalized Turán numbers for paths

2023-01-06

Doudou Hei , Xinmin Hou , Boyuan Liu

Generalized Turán problem with bounded matching number

2023-01-01

Yue Ma , Xinmin Hou

For a graph $T$ and a set of graphs $\mathcal{H}$, let $\ex(n,T,\mathcal{H})$ denote the maximum number of copies of $T$ in an $n$-vertex $\mathcal{H}$-free graph. Recently, Alon and Frankl~(arXiv2210.15076) determined … For a graph $T$ and a set of graphs $\mathcal{H}$, let $\ex(n,T,\mathcal{H})$ denote the maximum number of copies of $T$ in an $n$-vertex $\mathcal{H}$-free graph. Recently, Alon and Frankl~(arXiv2210.15076) determined the exact value of $\ex(n,K_2,\{K_{k+1},M_{s+1}\})$, where $K_{k+1}$ and $M_{s+1}$ are complete graph on $k+1$ vertices and matching of size $s+1$, respectively. Soon after, Gerbner~(arXiv2211.03272) continued the study by extending $K_{k+1}$ to general fixed graph $H$. In this paper, we continue the study of the function $\ex(n, T,\{H,M_{s+1}\})$ when $T=K_r$ for $r\ge 3$. We determine the exact value of $\ex(n,K_r,\{K_{k+1},M_{s+1}\})$ and give the value of $\ex(n,K_r,\{H,M_{s+1}\})$ for general $H$ with an error term $O(1)$.

Spectral extrema of graphs with bounded clique number and matching number

2023-01-01

Hongyu Wang , Xinmin Hou , Yue Ma

For a set of graphs $\mathcal{F}$, let $\ex(n,\mathcal{F})$ and $\spex(n,\mathcal{F})$ denote the maximum number of edges and the maximum spectral radius of an $n$-vertex $\mathcal{F}$-free graph, respectively. Nikiforov ({\em LAA}, … For a set of graphs $\mathcal{F}$, let $\ex(n,\mathcal{F})$ and $\spex(n,\mathcal{F})$ denote the maximum number of edges and the maximum spectral radius of an $n$-vertex $\mathcal{F}$-free graph, respectively. Nikiforov ({\em LAA}, 2007) gave the spectral version of the Tur\'an Theorem by showing that $\spex(n, K_{k+1})=\lambda (T_{k}(n))$, where $T_k(n)$ is the $k$-partite Tur\'an graph on $n$ vertices. In the same year, Feng, Yu and Zhang ({\em LAA}) determined the exact value of $\spex(n, M_{s+1})$, where $M_{s+1}$ is a matching with $s+1$ edges. Recently, Alon and Frankl~(arXiv2210.15076) gave the exact value of $\ex(n,\{K_{k+1},M_{s+1}\})$. In this article, we give the spectral version of the result of Alon and Frankl by determining the exact value of $\spex(n,\{K_{k+1},M_{s+1}\})$ when $n$ is large.

On Induced Subgraph of Cartesian Product of Paths

2023-01-01

Jiasheng Zeng , Xinmin Hou

Chung, F\"uredi, Graham, and Seymour (JCTA, 1988) constructed an induced subgraph of the hypercube $Q^n$ with $\alpha(Q^n)+1$ vertices and with maximum degree smaller than $\lceil \sqrt{n} \rceil$. Subsequently, Huang (Annals … Chung, F\"uredi, Graham, and Seymour (JCTA, 1988) constructed an induced subgraph of the hypercube $Q^n$ with $\alpha(Q^n)+1$ vertices and with maximum degree smaller than $\lceil \sqrt{n} \rceil$. Subsequently, Huang (Annals of Mathematics, 2019) proved the Sensitivity Conjecture by demonstrating that the maximum degree of such an induced subgraph of hypercube $Q^n$ is at least $\lceil \sqrt{n} \rceil$, and posed the question: Given a graph $G$, let $f(G)$ be the minimum of the maximum degree of an induced subgraph of $G$ on $\alpha(G)+1$ vertices, what can we say about $f(G)$? In this paper, we investigate this question for Cartesian product of paths $P_m$, denoted by $P_m^k$. We determine the exact values of $f(P_{m}^k)$ when $m=2n+1$ by showing that $f(P_{2n+1}^k)=1$ for $n\geq 2$ and $f(P_3^k)=2$, and give a nontrivial lower bound of $f(P_{m}^k)$ when $m=2n$ by showing that $f(P_{2n}^k)\geq \lceil \sqrt{\beta_nk}\rceil$. In particular, when $n=1$, we have $f(Q^k)=f(P_{2}^k)\ge \sqrt{k}$, which is Huang's result. The lower bounds of $f(P_{3}^k)$ and $f(P_{2n}^k)$ are given by using the spectral method provided by Huang.

View PDF Chat

Graphs without rainbow cliques of orders four and five

2023-01-01

Yue Ma , Xinmin Hou

Let $\mathcal{G}_n^k=\{G_1,G_2,\ldots,G_k\}$ be a multiset of graphs on vertex set $[n]$ and let $F$ be a fixed graph with edge set $F=\{e_1, e_2,\ldots, e_m\}$ and $k\ge m$. We say ${\mathcal{G}_n^k}$ … Let $\mathcal{G}_n^k=\{G_1,G_2,\ldots,G_k\}$ be a multiset of graphs on vertex set $[n]$ and let $F$ be a fixed graph with edge set $F=\{e_1, e_2,\ldots, e_m\}$ and $k\ge m$. We say ${\mathcal{G}_n^k}$ is rainbow $F$-free if there is no $\{i_1, i_2,\ldots, i_{m}\}\subseteq[k]$ satisfying $e_j\in G_{i_j}$ for every $j\in[m]$. Let $\ex_k(n,F)$ be the maximum $\sum_{i=1}^{k}|G_i|$ among all the rainbow $F$-free multisets ${\mathcal{G}_n^k}$. Keevash, Saks, Sudakov, and Verstra\"ete (2004) determined the exact value of $\ex_k(n, K_r)$ when $n$ is sufficiently large and proposed the conjecture that the results remain true when $n\ge Cr^2$ for some constant $C$. Recently, Frankl (2022) confirmed the conjecture for $r=3$ and all possible values of $n$. In this paper, we determine the exact value of $\ex_k(n, K_r)$ for $n\ge r-1$ when $r=4$ and $5$, i.e. the conjecture of Keevash, Saks, Sudakov, and Verstra\"ete is true for $r\in\{4,5\}$.

View PDF Chat

Graphs Without Rainbow Cliques of Orders Four and Five

2023-01-01

Yue Ma , Xinmin Hou

View PDF Chat

Multicolor Ramsey numbers on stars versus pat

2023-01-01

Xuejun Zhang , Xinmin Hou

For given simple graphs $H_1,H_2,\dots,H_c$, the multicolor Ramsey number $R(H_1,H_2,\dots,H_c)$ is defined as the smallest positive integer $n$ such that for an arbitrary edge-decomposition $\{G_i\}^c_{i=1}$ of the complete graph $K_n$, … For given simple graphs $H_1,H_2,\dots,H_c$, the multicolor Ramsey number $R(H_1,H_2,\dots,H_c)$ is defined as the smallest positive integer $n$ such that for an arbitrary edge-decomposition $\{G_i\}^c_{i=1}$ of the complete graph $K_n$, at least one $G_i$ has a subgraph isomorphic to $H_i$. Let $m,n_1,n_2,\dots,n_c$ be positive integers and $\Sigma=\sum_{i=1}^{c}(n_i-1)$. Some bounds and exact values of $R(K_{1,n_1},\dots,K_{1,n_c},P_m)$ have been obtained in literature. Wang (Graphs Combin., 2020) conjectured that if $\Sigma\not\equiv 0\pmod{m-1}$ and $\Sigma+1\ge (m-3)^2$, then $R(K_{1,n_1},\ldots, K_{1,n_c}, P_m)=\Sigma+m-1.$ In this note, we give a new lower bound and some exact values of $R(K_{1,n_1},\dots,K_{1,n_c},P_m)$ when $m\leq\Sigma$, $\Sigma\equiv k\pmod{m-1}$, and $2\leq k \leq m-2$. These results partially confirm Wang's conjecture.

View PDF Chat

The degree threshold for covering with all the connected $3$-graphs with $3$ edges

2023-01-01

Yue Ma , Xinmin Hou , Zhi Yin

Given two $r$-uniform hypergraphs $F$ and $H$, we say that $H$ has an $F$-covering if every vertex in $H$ is contained in a copy of $F$. Let $c_{i}(n,F)$ be the … Given two $r$-uniform hypergraphs $F$ and $H$, we say that $H$ has an $F$-covering if every vertex in $H$ is contained in a copy of $F$. Let $c_{i}(n,F)$ be the least integer such that every $n$-vertex $r$-graph $H$ with $\delta_{i}(H)>c_i(n,F)$ has an $F$-covering. Falgas-Ravry, Markst\"om and Zhao (Combin. Probab. Comput., 2021) asymptotically determined $c_1(n,K_{4}^{(3)-})$, where $K_{4}^{(3)-}$ is obtained by deleting an edge from the complete $3$-graph on $4$ vertices. Later, Tang, Ma and Hou (arXiv, 2022) asymptotically determined $c_1(n,C_{6}^{(3)})$, where $C_{6}^{(3)}$ is the linear triangle, i.e. $C_{6}^{(3)}=([6],\{123,345,561\})$. In this paper, we determine $c_1(n,F_5)$ asymptotically, where $F_5$ is the generalized triangle, i.e. $F_5=([5],\{123,124,345\})$. We also determine the exact values of $c_1(n,F)$, where $F$ is any connected $3$-graphs with $3$ edges and $F\notin\{K_4^{(3)-}, C_{6}^{(3)}, F_5\}$.

View PDF Chat

Ramsey numbers of color critical graphs versus large generalized fans

2023-01-01

Taiping Jiang , Xinmin Hou

Given two graphs $G$ and $H$, the {Ramsey number} $R(G,H)$ is the smallest positive integer $N$ such that every 2-coloring of the edges of $K_{N}$ contains either a red $G$ … Given two graphs $G$ and $H$, the {Ramsey number} $R(G,H)$ is the smallest positive integer $N$ such that every 2-coloring of the edges of $K_{N}$ contains either a red $G$ or a blue $H$. Let $K_{N-1}\sqcup K_{1,k}$ be the graph obtained from $K_{N-1}$ by adding a new vertex $v$ connecting $k$ vertices of $K_{N-1}$. Hook and Isaak (2011) defined the {\em star-critical Ramsey number} $r_{*}(G,H)$ as the smallest integer $k$ such that every 2-coloring of the edges of $K_{N-1}\sqcup K_{1,k}$ contains either a red $G$ or a blue $H$, where $N=R(G, H)$. For sufficiently large $n$, Li and Rousseau~(1996) proved that $R(K_{k+1},K_{1}+nK_{t})=knt +1$, Hao, Lin~(2018) showed that $r_{*}(K_{k+1},K_{1}+nK_{t})=(k-1)tn+t$; Li and Liu~(2016) proved that $R(C_{2k+1}, K_{1}+nK_{t})=2nt+1$, and Li, Li, and Wang~(2020) showed that $r_{*}(C_{2m+1},K_{1}+nK_{t})=nt+t$. A graph $G$ with $\chi(G)=k+1$ is called edge-critical if $G$ contains an edge $e$ such that $\chi(G-e)=k$. In this paper, we extend the above results by showing that for an edge-critical graph $G$ with $\chi(G)=k+1$, when $k\geq 2$, $t\geq 2$ and $n$ is sufficiently large, $R(G, K_{1}+nK_{t})=knt+1$ and $r_{*}(G,K_{1}+nK_{t})=(k-1)nt+t$.

View PDF Chat

Counting triangles in regular graphs

2023-01-01

Jialin He , Xinmin Hou , Jie Ma +1 more

In this paper, we investigate the minimum number of triangles, denoted by $t(n,k)$, in $n$-vertex $k$-regular graphs, where $n$ is an odd integer and $k$ is an even integer. The … In this paper, we investigate the minimum number of triangles, denoted by $t(n,k)$, in $n$-vertex $k$-regular graphs, where $n$ is an odd integer and $k$ is an even integer. The well-known Andr\'asfai-Erd\H{o}s-S\'os Theorem has established that $t(n,k)>0$ if $k>\frac{2n}{5}$. In a striking work, Lo has provided the exact value of $t(n,k)$ for sufficiently large $n$, given that $\frac{2n}{5}+\frac{12\sqrt{n}}{5}<k<\frac{n}{2}$. Here, we bridge the gap between the aforementioned results by determining the precise value of $t(n,k)$ in the entire range $\frac{2n}{5}<k<\frac{n}{2}$. This confirms a conjecture of Cambie, de Joannis de Verclos, and Kang for sufficiently large $n$.

View PDF Chat

A new connectivity bound for a tournament to be highly linked

2023-01-01

Bin Chen , Xinmin Hou , Gexin Yu +1 more

A digraph $D$ is $k$-linked if for any pair of two disjoint sets $\{x_{1},x_{2},\ldots,x_{k}\}$ and $\{y_{1},y_{2},\ldots,y_{k}\}$ of vertices in $D$, there exist vertex disjoint dipaths $P_{1},P_{2},\ldots,P_{k}$ such that $P_{i}$ is … A digraph $D$ is $k$-linked if for any pair of two disjoint sets $\{x_{1},x_{2},\ldots,x_{k}\}$ and $\{y_{1},y_{2},\ldots,y_{k}\}$ of vertices in $D$, there exist vertex disjoint dipaths $P_{1},P_{2},\ldots,P_{k}$ such that $P_{i}$ is a dipath from $x_{i}$ to $y_{i}$ for each $i\in[k]$. Pokrovskiy (JCTB, 2015) confirmed a conjecture of K\"{u}hn et al. (Proc. Lond. Math. Soc., 2014) by verifying that every $452k$-connected tournament is $k$-linked. Meng et al. (Eur. J. Comb., 2021) improved this upper bound by showing that any $(40k-31)$-connected tournament is $k$-linked. In this paper, we show a better upper bound by proving that every $\lceil 12.5k-6\rceil$-connected tournament with minimum out-degree at least $21k-14$ is $k$-linked. Furthermore, we improve a key lemma that was first introduced by Pokrovskiy (JCTB, 2015) and later enhanced by Meng et al. (Eur. J. Comb., 2021).

An improved probability propagation algorithm for density peak clustering based on natural nearest neighborhood

2022-07-18

Wendi Zuo , Xinmin Hou

View PDF Chat

Rainbow independent sets in graphs with maximum degree two

2022-05-18

Yue Ma , Xinmin Hou , Jun Gao +2 more

View PDF Chat

Strongly Connected Orientation with Minimum Lexicographic Order of Indegrees

2022-02-01

Hongyu Zhou , Xinmin Hou

View PDF Chat

A note on shortest circuit cover of 3-edge colorable cubic signed graphs

2022-01-01

Ronggui Xu , Jiaao Li , Xinmin Hou

A {sign-circuit cover} $\mathcal{F}$ of a signed graph $(G, \sigma)$ is a family of sign-circuits which covers all edges of $(G, \sigma)$. The shortest sign-circuit cover problem was initiated by … A {sign-circuit cover} $\mathcal{F}$ of a signed graph $(G, \sigma)$ is a family of sign-circuits which covers all edges of $(G, \sigma)$. The shortest sign-circuit cover problem was initiated by M\'a$\check{\text{c}}$ajov\'a, Raspaud, Rollov\'a, and \v{S}koviera (JGT 2016) and received many attentions in recent years. In this paper, we show that every flow-admissible 3-edge colorable cubic signed graph $(G, \sigma)$ has a sign-circuit cover with length at most $\frac{20}{9} |E(G)|$.

View PDF Chat

Maximal fractional cross-intersecting families

2022-01-01

Hongkui Wang , Xinmin Hou

Given an irreducible fraction $\frac{c}{d} \in [0,1]$, a pair $(\mathcal{A},\mathcal{B})$ is called a $\frac{c}{d}$-cross-intersecting pair of $2^{[n]}$ if $\mathcal{A}, \mathcal{B}$ are two families of subsets of $[n]$ such that for … Given an irreducible fraction $\frac{c}{d} \in [0,1]$, a pair $(\mathcal{A},\mathcal{B})$ is called a $\frac{c}{d}$-cross-intersecting pair of $2^{[n]}$ if $\mathcal{A}, \mathcal{B}$ are two families of subsets of $[n]$ such that for every pair $A \in\mathcal{A}$ and $B\in\mathcal{B}$, $|A \cap B|= \frac{c}{d}|B|$. Mathew, Ray, and Srivastava [{\it\small Fractional cross intersecting families, Graphs and Comb., 2019}] proved that $|\mathcal{A}||\mathcal{B}|\le 2^n$ if $(\mathcal{A}, \mathcal{B})$ is a $\frac{c}{d}$-cross-intersecting pair of $2^{[n]}$ and characterized all the pairs $(\mathcal{A},\mathcal{B})$ with $|\mathcal{A}||\mathcal{B}|=2^n$, such a pair also is called a maximal $\frac cd$-cross-intersecting pair of $2^{[n]}$, when $\frac cd\in\{0,\frac12, 1\}$. In this note, we characterize all the maximal $\frac cd$-cross-intersecting pairs $(\mathcal{A},\mathcal{B})$ when $0<\frac{c}{d}<1$ and $\frac cd\not=\frac 12$, this result answers a question proposed by Mathew, Ray, and Srivastava (2019).

View PDF Chat

Pancyclicity of randomly perturbed digraph

2022-01-01

Zelin Ren , Xinmin Hou

Dirac’s theorem states that if a graph G on n vertices has a minimum degree of at least <inline-formula><tex-math id="M1">\begin{document}$\displaystyle \frac{n}{2}$\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M1.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M1.png"/></alternatives></inline-formula>, then G contains a Hamiltonian … Dirac’s theorem states that if a graph G on n vertices has a minimum degree of at least <inline-formula><tex-math id="M1">\begin{document}$\displaystyle \frac{n}{2}$\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M1.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M1.png"/></alternatives></inline-formula>, then G contains a Hamiltonian cycle. Bohman et al. introduced the random perturbed graph model and proved that for any constant <inline-formula><tex-math id="M2">\begin{document}$ \alpha > 0 $\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M2.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M2.png"/></alternatives></inline-formula> and a graph H with a minimum degree of at least <inline-formula><tex-math id="M3">\begin{document}$ \alpha n $\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M3.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M3.png"/></alternatives></inline-formula>, there exists a constant C depending on α such that for any <inline-formula><tex-math id="M4">\begin{document}$p \geqslant \dfrac{C}{n}$\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M4.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M4.png"/></alternatives></inline-formula>, <inline-formula><tex-math id="M5">\begin{document}$H \cup {G_{n,p}}$\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M5.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M5.png"/></alternatives></inline-formula> is asymptotically almost surely (a.a.s.) Hamiltonian. In this study, the random perturbed digraph model is considered, and we show that for all <inline-formula><tex-math id="M6">\begin{document}$\alpha = \omega \left( {{{\left( {\dfrac{{\log n}}{n}} \right)}^{{\textstyle{1 \over 4}}}}} \right)$\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M6.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M6.png"/></alternatives></inline-formula> and <inline-formula><tex-math id="M7">\begin{document}$d \in \{ 1,2\}$\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M7.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M7.png"/></alternatives></inline-formula>, the union of a digraph on n vertices with a minimum degree of at least <inline-formula><tex-math id="M8">\begin{document}$ \alpha n $\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M8.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M8.png"/></alternatives></inline-formula> and a random d-regular digraph on n vertices is a.a.s. pancyclic. Moreover, a polynomial-time algorithm is proposed to find cycles of any length in such a digraph.

Minimizing the number of matchings of fixed size in a $K_s$-saturated graph

2022-01-01

Jiejing Feng , Doudou Hei , Xinmin Hou

For a fixed graph $F$, a graph $G$ is said to be $F$-saturated if $G$ does not contain a subgraph isomorphic to $F$ but does contain $F$ after the addition … For a fixed graph $F$, a graph $G$ is said to be $F$-saturated if $G$ does not contain a subgraph isomorphic to $F$ but does contain $F$ after the addition of any new edge. Let $M_k$ be a matching consisting of $k$ edges and $S_{n,k}$ be the join graph of a complete graph $K_k$ and an empty graph $\overline{K_{n-k}}$. In this paper, we prove that for $s \geq3$ and $k\geq 2$, $S_{n,s-2}$ contains the minimum number of $M_k$ among all $n$-vertex $K_s$-saturated graphs for sufficiently large $n$, and when $k \leq s-2$, it is the unique extremal graph. In addition, we also show that $S_{n,1}$ is the unique extremal graph when $k=2$ and $s=3$.

View PDF Chat

Maximum size of $C_{\leq k}$-free strong digraphs with out-degree at least two

2022-01-01

Bin Chen , Xinmin Hou

Let $\mathscr{H}$ be a family of digraphs. A digraph $D$ is \emph{$\mathscr{H}$-free} if it contains no isomorphic copy of any member of $\mathscr{H}$. For $k\geq2$, we set $C_{\leq k}=\{C_{2}, C_{3},\ldots,C_{k}\}$, … Let $\mathscr{H}$ be a family of digraphs. A digraph $D$ is \emph{$\mathscr{H}$-free} if it contains no isomorphic copy of any member of $\mathscr{H}$. For $k\geq2$, we set $C_{\leq k}=\{C_{2}, C_{3},\ldots,C_{k}\}$, where $C_{\ell}$ is a directed cycle of length $\ell\in\{2,3,\ldots,k\}$. Let $D_{n}^{k}(\xi,\zeta)$ denote the family of \emph{${C}_{\le k}$-free} strong digraphs on $n$ vertices with every vertex having out-degree at least $\xi$ and in-degree at least $\zeta$, where both $\xi$ and $\zeta$ are positive integers. Let $\varphi_{n}^{k}(\xi,\zeta)=\max\{|A(D)|:\;D\in D_{n}^{k}(\xi,\zeta)\}$ and $\Phi_{n}^{k}(\xi,\zeta)=\{D\in D_{n}^{k}(\xi,\zeta): |A(D)|=\varphi_{n}^{k}(\xi,\zeta)\}$. Bermond et al.\;(1980) verified that $\varphi_{n}^{k}(1,1)=\binom{n-k+2}{2}+k-2$. Chen and Chang\;(2021) showed that $\binom{n-1}{2}-2\leq\varphi_{n}^{3}(2,1)\leq\binom{n-1}{2}$. This upper bound was further improved to $\binom{n-1}{2}-1$ by Chen and Chang\;(DAM, 2022), furthermore, they also gave the exact values of $\varphi_{n}^{3}(2,1)$ for $n\in \{7,8,9\}$. In this paper, we continue to determine the exact values of $\varphi_{n}^{3}(2,1)$ for $n\ge 10$, i.e., $\varphi_{n}^{3}(2,1)=\binom{n-1}{2}-2$ for $n\geq10$.

The degree and codegree threshold for linear triangle covering in 3-graphs

2022-01-01

Yuxuan Tang , Yue Ma , Xinmin Hou

Given two $k$-uniform hypergraphs $F$ and $G$, we say that $G$ has an $F$-covering if every vertex in $G$ is contained in a copy of $F$. For $1\le i \le … Given two $k$-uniform hypergraphs $F$ and $G$, we say that $G$ has an $F$-covering if every vertex in $G$ is contained in a copy of $F$. For $1\le i \le k-1$, let $c_i(n,F)$ be the least integer such that every $n$-vertex $k$-uniform hypergraph $G$ with $\delta_i(G)> c_i(n,F)$ has an $F$-covering. The covering problem has been systematically studied by Falgas-Ravry and Zhao [Codegree thresholds for covering 3-uniform hypergraphs, SIAM J. Discrete Math., 2016]. Last year, Falgas-Ravry, Markstr\"om, and Zhao [Triangle-degrees in graphs and tetrahedron coverings in 3-graphs, Combinatorics, Probability and Computing, 2021] asymptotically determined $c_1(n, F)$ when $F$ is the generalized triangle. In this note, we give the exact value of $c_2(n, F)$ and asymptotically determine $c_1(n, F)$ when $F$ is the linear triangle $C_6^3$, where $C_6^3$ is the 3-uniform hypergraph with vertex set $\{v_1,v_2,v_3,v_4,v_5,v_6\}$ and edge set $\{v_1v_2v_3,v_3v_4v_5,v_5v_6v_1\}$.

View PDF Chat

An Improved Probability Propagation Algorithm for Density Peak Clustering Based on Natural Nearest Neighborhood

2022-01-01

Wendi Zuo , Xinmin Hou

Clustering by fast search and find of density peaks (DPC) (Since, 2014) has been proven to be a promising clustering approach that efficiently discovers the centers of clusters by finding … Clustering by fast search and find of density peaks (DPC) (Since, 2014) has been proven to be a promising clustering approach that efficiently discovers the centers of clusters by finding the density peaks. The accuracy of DPC depends on the cutoff distance ($d_c$), the cluster number ($k$) and the selection of the centers of clusters. Moreover, the final allocation strategy is sensitive and has poor fault tolerance. The shortcomings above make the algorithm sensitive to parameters and only applicable for some specific datasets. To overcome the limitations of DPC, this paper presents an improved probability propagation algorithm for density peak clustering based on the natural nearest neighborhood (DPC-PPNNN). By introducing the idea of natural nearest neighborhood and probability propagation, DPC-PPNNN realizes the nonparametric clustering process and makes the algorithm applicable for more complex datasets. In experiments on several datasets, DPC-PPNNN is shown to outperform DPC, K-means and DBSCAN.

View PDF Chat

The cycle of length four is strictly $F$-Turán-good

2022-01-01

Doudou Hei , Xinmin Hou

Given an $(r+1)$-chromatic graph $F$ and a graph $H$ that does not contain $F$ as a subgraph, we say that $H$ is strictly $F$-Tur\'an-good if the Tur\'an graph $T_{r}(n)$ is … Given an $(r+1)$-chromatic graph $F$ and a graph $H$ that does not contain $F$ as a subgraph, we say that $H$ is strictly $F$-Tur\'an-good if the Tur\'an graph $T_{r}(n)$ is the unique graph containing the maximum number of copies of $H$ among all $F$-free graphs on $n$ vertices for every $n$ large enough. Gy\H{o}ri, Pach and Simonovits (1991) proved that cycle $C_4$ of length four is strictly $K_{r+1}$-Tur\'{a}n-good for all $r\geq 2$. In this article, we extend this result and show that $C_4$ is strictly $F$-Tur\'an-good, where $F$ is an $(r+1)$-chromatic graph with $r\ge 2$ and a color-critical edge. Moreover, we show that every $n$-vertex $C_4$-free graph $G$ with $N(H,G)=\ex(n,C_4,F)-o(n^4)$ can be obtained by adding or deleting $o(n^2)$ edges from $T_r(n)$. Our proof uses the flag algebra method developed by Razborov (2007).

View PDF Chat

The Turán number for the edge blow-up of trees

2021-09-16

Anyao Wang , Xinmin Hou , Boyuan Liu +1 more

Maximizing the number of independent sets of fixed size in Kn‐covered graphs

2021-08-10

Anyao Wang , Xinmin Hou , Boyuan Liu +1 more

Abstract For some given graph , a graph is called ‐covered if each vertex in is contained in a copy of . In this note, we determine the maximum number … Abstract For some given graph , a graph is called ‐covered if each vertex in is contained in a copy of . In this note, we determine the maximum number of independent sets of size in ‐vertex ‐covered graphs and classify the extremal graphs. The result answers a question proposed by Chakraborti and Loh. The proof uses an edge‐switching operation on hypergraphs which never increases the number of independent sets.

View PDF Chat

Minimizing the number of edges in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.svg"><mml:msub><mml:mrow><mml:mi mathvariant="script">C</mml:mi></mml:mrow><mml:mrow><mml:mo>≥</mml:mo><mml:mi>r</mml:mi></mml:mrow></mml:msub></mml:math>-saturated graphs

2021-08-02

Yue Ma , Xinmin Hou , Doudou Hei +1 more

Some exact results of the generalized Turán numbers for paths

2021-01-01

Doudou Hei , Xinmin Hou , Boyuan Liu

For graphs $H$ and $F$ with chromatic number $\chi(F)=k$, we call $H$ strictly $F$-Tur\'an-good (or $(H, F)$ strictly Tur\'an-good) if the Tur\'an graph $T_{k-1}(n)$ is the unique $F$-free graph on … For graphs $H$ and $F$ with chromatic number $\chi(F)=k$, we call $H$ strictly $F$-Tur\'an-good (or $(H, F)$ strictly Tur\'an-good) if the Tur\'an graph $T_{k-1}(n)$ is the unique $F$-free graph on $n$ vertices containing the largest number of copies of $H$ when $n$ is large enough. Let $F$ be a graph with chromatic number $\chi(F)\geq 3$ and a color-critical edge and let $P_\ell$ be a path with $\ell$ vertices. Gerbner and Palmer (2020, arXiv:2006.03756) showed that $(P_3, F)$ is strictly Tur\'an good if $\chi(H)\ge 4$ and they conjectured that (a) this result is true when $\chi(F)=3$, and, moreover, (b) $(P_\ell, K_k)$ is Tur\'an-good for every pair of integers $\ell$ and $k$. In the present paper, we show that $(H, F)$ is strictly Tur\'an-good when $H$ is a bipartite graph with matching number $\nu(H)=\lfloor \frac{|V(H)|}{2}\rfloor$ and $\chi(F)= 3$, as a corollary, this result confirms the conjecture (a); we also prove that $(P_\ell, F)$ is strictly Tur\'an-good for $2\le\ell\leq 6$ and $\chi(F)\ge 4$, this also confirms the conjecture (b) for $2\le\ell\leq 6$ and $k\ge 4$.

View PDF Chat

Strongly connected orientation with minimum lexicographic order of indegrees

2021-01-01

Hongyu Zhou , Xinmin Hou

Given a simple undirected graph $G$, an orientation of $G$ is to assign every edge of $G$ a direction. Borradaile et al gave a greedy algorithm SC-Path-Reversal (in polynomial time) … Given a simple undirected graph $G$, an orientation of $G$ is to assign every edge of $G$ a direction. Borradaile et al gave a greedy algorithm SC-Path-Reversal (in polynomial time) which finds a strongly connected orientation that minimizes the maximum indegree, and conjectured that SC-Path-Reversal is indeed optimal for the "minimizing the lexicographic order" objective as well. In this note, we give a positive answer to the conjecture, that is we show that the algorithm SC-PATH-REVERSAL finds a strongly connected orientation that minimizes the lexicographic order of indegrees.

View PDF Chat

Rainbow independent sets in graphs with maximum degree two

2021-01-01

Yue Ma , Xinmin Hou , Jun Gao +2 more

Given a graph $G$, let $f_{G}(n,m)$ be the minimal number $k$ such that every $k$ independent $n$-sets in $G$ have a rainbow $m$-set. Let $\mathcal{D}(2)$ be the family of all … Given a graph $G$, let $f_{G}(n,m)$ be the minimal number $k$ such that every $k$ independent $n$-sets in $G$ have a rainbow $m$-set. Let $\mathcal{D}(2)$ be the family of all graphs with maximum degree at most two. Aharoni et al. (2019) conjectured that (i) $f_G(n,n-1)=n-1$ for all graphs $G\in\mathcal{D}(2)$ and (ii) $f_{C_t}(n,n)=n$ for $t\ge 2n+1$. Lv and Lu (2020) showed that the conjecture (ii) holds when $t=2n+1$. In this article, we show that the conjecture (ii) holds for $t\ge\frac{1}{3}n^2+\frac{44}{9}n$. Let $C_t$ be a cycle of length $t$ with vertices being arranged in a clockwise order. An ordered set $I=(a_1,a_2,\ldots,a_n)$ on $C_t$ is called a $2$-jump independent $n$-set of $C_t$ if $a_{i+1}-a_i=2\pmod{t}$ for any $1\le i\le n-1$. We also show that a collection of 2-jump independent $n$-sets $\mathcal{F}$ of $C_t$ with $|\mathcal{F}|=n$ admits a rainbow independent $n$-set, i.e. (ii) holds if we restrict $\mathcal{F}$ on the family of 2-jump independent $n$-sets. Moreover, we prove that if the conjecture (ii) holds, then (i) holds for all graphs $G\in\mathcal{D}(2)$ with $c_e(G)\le 4$, where $c_e(G)$ is the number of components of $G$ isomorphic to cycles of even lengths.

Codegree Threshold for Tiling Balanced Complete $3$-Partite $3$-Graphs and Generalized $4$-Cycles

2020-09-04

Xinmin Hou , Boyuan Liu , Yue Ma

Given two $k$-graphs $F$ and $H$, a perfect $F$-tiling (also called an $F$-factor) in $H$ is a set of vertex-disjoint copies of $F$ that together cover the vertex set of … Given two $k$-graphs $F$ and $H$, a perfect $F$-tiling (also called an $F$-factor) in $H$ is a set of vertex-disjoint copies of $F$ that together cover the vertex set of $H$. Let $t_{k-1}(n, F)$ be the smallest integer $t$ such that every $k$-graph $H$ on $n$ vertices with minimum codegree at least $t$ contains a perfect $F$-tiling. Mycroft (JCTA, 2016) determined the asymptotic values of $t_{k-1}(n, F)$ for $k$-partite $k$-graphs $F$ and conjectured that the error terms $o(n)$ in $t_{k-1}(n, F)$ can be replaced by a constant that depends only on $F$. In this paper, we determine the exact value of $t_2(n, K_{m,m}^{3})$, where $K_{m,m}^{3}$ (defined by Mubayi and Verstraëte, JCTA, 2004) is the 3-graph obtained from the complete bipartite graph $K_{m,m}$ by replacing each vertex in one part by a 2-elements set. Note that $K_{2,2}^{3}$ is the well known generalized 4-cycle $C_4^3$ (the 3-graph on six vertices and four distinct edges $A, B, C, D$ with $A\cup B= C\cup D$ and $A\cap B=C\cap D=\emptyset$). The result confirms Mycroft's conjecture for $K_{m,m}^{3}$. Moreover, we improve the error term $o(n)$ to a sub-linear term when $F=K^3(m)$ and show that the sub-linear term is tight for $K^3(2)$, where $K^3(m)$ is the complete $3$-partite $3$-graph with each part of size $m$.

View PDF Chat

Exact Minimum Codegree Thresholds for $K_4^-$-Covering and $K_5^-$-Covering

2020-08-07

Lei Yu , Xinmin Hou , Yue Ma +1 more

View PDF Chat

Minimum degree of 3-graphs without long linear paths

2020-05-19

Yue Ma , Xinmin Hou , Jun Gao

View PDF Chat

Exact minimum codegree thresholds for $K_4^-$-covering and $K_5^-$-covering

2020-01-01

Lei Yu , Xinmin Hou , Boyuan Liu +1 more

Given two $3$-graphs $F$ and $H$, an $F$-covering of $H$ is a collection of copies of $F$ in $H$ such that each vertex of $H$ is contained in at least … Given two $3$-graphs $F$ and $H$, an $F$-covering of $H$ is a collection of copies of $F$ in $H$ such that each vertex of $H$ is contained in at least one copy of them. Let {$c_2(n,F)$} be the maximum integer $t$ such that every 3-graph with minimum codegree greater than $t$ has an $F$-covering. In this note, we answer an open problem of Falgas-Ravry and Zhao (SIAM J. Discrete Math., 2016) by determining the exact value of {$c_2(n, K_4^-)$} and {$c_2(n, K_5^-)$}, where $K_t^-$ is the complete $3$-graph on $t$ vertices with one edge removed.

Maximizing the number of independent sets of fixed size in $K_n$-covered graphs

2020-01-01

Anyao Wang , Xinmin Hou , Boyuan Liu +1 more

View PDF Chat

Minimizing the number of edges in $\mathcal{C}_{\ge r}$-saturated graphs

2020-01-01

Yue Ma , Xinmin Hou , Doudou Hei +1 more

Given a family of graphs $\mathcal{F}$, a graph $G$ is said to be $\mathcal{F}$-saturated if $G$ does not contain a copy of $F$ as a subgraph for any $F\in\mathcal{F}$ but … Given a family of graphs $\mathcal{F}$, a graph $G$ is said to be $\mathcal{F}$-saturated if $G$ does not contain a copy of $F$ as a subgraph for any $F\in\mathcal{F}$ but the addition of any edge $e\notin E(G)$ creates at least one copy of some $F\in\mathcal{F}$ within $G$. The minimum size of an $\mathcal{F}$-saturated graph on $n$ vertices are called the saturation number, denoted by $\sat(n, \mathcal{F})$. Let $\mathcal{C}_{\ge r}$ be the family of cycles of length at least $r$. Ferrara et al. (2012) gave lower and upper bounds of $\sat(n, C_{\ge r})$ and determined the exact values of $\sat(n, C_{\ge r})$ for $3\le r\le 5$. In this paper, we determine the exact value of $\sat(n,\mathcal{C}_{\ge r})$ for $r=6$ and $28\le \frac{n}2\le r\le n$ and give new upper and lower bounds for the other cases.

Coauthor	Papers Together
Yue Ma	27
Boyuan Liu	24
Jun Gao	15
Lei Yu	8
Doudou Hei	7
Jiaao Li	6
Yu Qiu	6
Anyao Wang	4
Jun‐Ming Xu	4
Hongyu Zhou	3
Bin Chen	3
Boyuan Liu	3
Hongkui Wang	3
Zhi Yin	3
Xinyu Zhou	2
Cun‐Quan Zhang	2
Hongliang Lu	2
Wendi Zuo	2
Hong‐Jian Lai	2
Min Xu	2
Yuxuan Tang	2
Tianying Xie	2
Jie Ma	2
Ning Li	2
You Lu	2
Zhen‐Mu Hong	2
Chenhui Lv	2
Zelin Ren	1
Xiaodong Xue	1
Shicheng Wang	1
Zhi Yin	1
Yang Yang	1
Xuejun Zhang	1
Miaomiao Han	1
Taiping Jiang	1
Hongyu Wang	1
Xinkai Tao	1
Rui Yang	1
Ronggui Xu	1
Wei Zhong	1
Jialin He	1
Gexin Yu	1
Jiejing Feng	1
Ning Li	1
Xiaofeng Ding	1
Min Xu	1
Yuming Zhang	1
Hongyu Wang	1
Bin Chen	1
Jin Sun	1