BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
A {sign-circuit cover} F of a signed graph (G,σ) is a family of sign-circuits which covers all edges of (G,σ). The shortest sign-circuit cover problem was initiated by Mácˇajová, Raspaud, Rollová, and Š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,σ) has a sign-circuit cover with length at most 920∣E(G)∣.
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 (dc), 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.
Given an irreducible fraction dc∈[0,1], a pair (A,B) is called a dc-cross-intersecting pair of 2[n] if A,B are two families of subsets of [n] such that for every pair A∈A and B∈B, ∣A∩B∣=dc∣B∣. Mathew, Ray, and Srivastava [{\it\small Fractional cross intersecting families, Graphs and Comb., 2019}] proved that ∣A∣∣B∣≤2n if (A,B) is a dc-cross-intersecting pair of 2[n] and characterized all the pairs (A,B) with ∣A∣∣B∣=2n, such a pair also is called a maximal dc-cross-intersecting pair of 2[n], when dc∈{0,21,1}. In this note, we characterize all the maximal dc-cross-intersecting pairs (A,B) when 0<dc<1 and dc=21, this result answers a question proposed by Mathew, Ray, and Srivastava (2019).
For graphs H and F with chromatic number χ(F)=k, we call H strictly F-Turán-good (or (H,F) strictly Turán-good) if the Turán graph Tk−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 χ(F)≥3 and a color-critical edge and let Pℓ be a path with ℓ vertices. Gerbner and Palmer (2020, arXiv:2006.03756) showed that (P3,F) is strictly Turán good if χ(H)≥4 and they conjectured that (a) this result is true when χ(F)=3, and, moreover, (b) (Pℓ,Kk) is Turán-good for every pair of integers ℓ and k. In the present paper, we show that (H,F) is strictly Turán-good when H is a bipartite graph with matching number ν(H)=⌊2∣V(H)∣⌋ and χ(F)=3, as a corollary, this result confirms the conjecture (a); we also prove that (Pℓ,F) is strictly Turán-good for 2≤ℓ≤6 and χ(F)≥4, this also confirms the conjecture (b) for 2≤ℓ≤6 and k≥4.
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án-good if the Turán graph Tr(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őri, Pach and Simonovits (1991) proved that cycle C4 of length four is strictly Kr+1-Turán-good for all r≥2. In this article, we extend this result and show that C4 is strictly F-Turán-good, where F is an (r+1)-chromatic graph with r≥2 and a color-critical edge. Moreover, we show that every n-vertex C4-free graph G with $N(H,G)=\ex(n,C_4,F)-o(n^4)$ can be obtained by adding or deleting o(n2) edges from Tr(n). Our proof uses the flag algebra method developed by Razborov (2007).
Given a family of graphs F, a graph G is said to be F-saturated if G does not contain a copy of F as a subgraph for any F∈F but the addition of any edge e∈/E(G) creates at least one copy of some F∈F within G. The minimum size of an F-saturated graph on n vertices are called the saturation number, denoted by $\sat(n, \mathcal{F})$. Let C≥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≤r≤5. In this paper, we determine the exact value of $\sat(n,\mathcal{C}_{\ge r})$ for r=6 and 28≤2n≤r≤n and give new upper and lower bounds for the other cases.
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.
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 {c2(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 {c2(n,K4−)} and {c2(n,K5−)}, where Kt− is the complete 3-graph on t vertices with one edge removed.
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≥3 in Kn-covered graphs of size N≥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.
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án problem for the edge blow-up of trees. Erdő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án problem for the edge blow-up of trees is completely resolved. Moreover, we determine the maximum number of edges in the family of {K1,k,kK2,2K1,k−1}-free graphs and the extremal graphs, which is an extension of a result given by Abbott et al. (1972).
Let ϕ(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 ϕ(n,H) parts, of which every part either is a single edge or forms a graph isomorphic to H. Pikhurko and Sousa conjectured that $ϕ(n,H)=\ex(n,H)$ for $χ(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.
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 Tn,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 Tn,r is the only extremal graph for complete graph Kr+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.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.