Let $\mathcal{F}=\{H_1, \ldots, H_k\}$ ($k\ge 1$) be a family of graphs. The Turán number of the family $\mathcal{F}$ is the maximum number of edges in an $n$-vertex $\{H_1, \ldots, H_k\}$-free graph, denoted by ex$(n, \mathcal{F})$ or ex$(n, \{H_1,H_2,\ldots,H_k\})$. The blow-up of a graph $H$ is the graph obtained from $H$ by replacing each edge in $H$ by a clique of the same size where the new vertices of the cliques are all different. In this paper we determine the Turán number of the family consisting of a blow-up of a cycle and a blow-up of a star in terms of the Turán number of the family consisting of a cycle, a star and linear forests with $k$ edges.

Let $G$ be a simple graph with $2n$ vertices and a perfect matching. The forcing number $f(G,M)$ of a perfect matching $M$ of $G$ is the smallest cardinality of a subset of $M$ that is contained in no other perfect matching of $G$. Among all perfect matchings $M$ of $G$, the minimum and maximum values of $f(G,M)$ are called the minimum and maximum forcing numbers of $G$, denoted by $f(G)$ and $F(G)$, respectively. Then $f(G)\leq F(G)\leq n-1$. Che and Chen (2011) proposed an open problem: how to characterize the graphs $G$ with $f(G)=n-1$. Later they showed that for a bipartite graph $G$, $f(G)=n-1$ if and only if $G$ is complete bipartite graph $K_{n,n}$. In this paper, we completely solve the problem of Che and Chen, and show that $f(G)=n-1$ if and only if $G$ is a complete multipartite graph or a graph obtained from complete bipartite graph $K_{n,n}$ by adding arbitrary edges in one partite set. For all graphs $G$ with $F(G)=n-1$, we prove that the forcing spectrum of each such graph $G$ forms an integer interval by matching 2-switches and the minimum forcing numbers of all such graphs $G$ form an integer interval from $\lfloor\frac{n}{2}\rfloor$ to $n-1$.

A hypergraph $\mathcal{H}$ is an {\em $(n,m)$-hypergraph} if it contains $n$ vertices and $m$ hyperedges, where $n\geq 1$ and $m\geq 0$ are two integers. Let $k$ be a positive integer and let $L$ be a set of nonnegative integers. A hypergraph $\mathcal{H}$ is {\em $k$-uniform} if all its hyperedges have the same size $k$, and $\mathcal{H}$ is {\em $L$-intersecting} if the number of common vertices of every two hyperedges belongs to $L$. In this paper, we propose and investigate the problem of estimating the maximum $k$ among all $k$-uniform $L$-intersecting $(n,m)$-hypergraphs for fixed $n,m$ and $L$. We will provide some tight upper and lower bounds on $k$ in terms of $n,m$ and $L$.

A Steinberg-type conjecture on circular coloring is recently proposed that for any prime p ≥ 5, every planar graph of girth p without cycles of length from p+1 to p(p-2) is C_p-colorable (that is, it admits a homomorphism to the odd cycle C_p). The assumption of p ≥ 5 being prime number is necessary, and this conjecture implies a special case of Jaeger’s Conjecture that every planar graph of girth 2p - 2 is C_p-colorable for prime p ≥ 5. In this paper, combining our previous results, we show the fractional coloring version of this conjecture is true. Particularly, the p = 5 case of our fractional coloring result shows that every planar graph of girth 5 without cycles of length from 6 to 15 admits a homomorphism to the Petersen graph.

For a finite group G, the power graph P(G) is a simple connected graph whose vertex set is the set of elements of G and two distinct vertices x and y are adjacent if and only if xⁱ = y or y^j = x, for 2 ≤ i, j ≤ n. In this paper, we obtain the distance Laplacian spectrum of power graphs of finite groups such as cyclic groups, dihedral groups, dicyclic groups, abelian groups and elementary abelian p groups. Moreover, we find the largest and second smallest distance Laplacian eigenvalue of power graphs of such groups.

The Merrifield-Simmons index σ is the total number of independent vertex sets (including the empty set) of the graph G. The Wiener index W is the sum of distances in all unordered pairs of vertices of G. We construct some new graphs satisfying σ > W and W > σ, respectively. In particular, infinite graphs satisfying W > σ are invented with graphs with diameter 2 and infinite ones satisfying σ > W are discovered with so-called universally diametrical graphs.

Given a graph $G$ and a positive integer $k$, define the Gallai-Ramsey number to be the minimum number of vertices $n$ such that any $k$-edge coloring of $K_n$ contains either a rainbow (all different colored) triangle or a monochromatic copy of $G$. In this paper, we obtain exact values of the Gallai-Ramsey numbers for the union of two stars in many cases and bounds in other cases. This work represents the first class of disconnected graphs to be considered as the desired monochromatic subgraph.

For $0 \leq \alpha < 1$, the $\alpha$-spectral radius of an $r$-uniform hypergraph $G$ is the spectral radius of $\mathcal{A}_{\alpha}(G)=\alpha \mathcal{D}(G)+(1-\alpha)\mathcal{A}(G)$, where $\mathcal{D}(G)$ and $\mathcal{A}(G)$ are the diagonal tensor of degrees and adjacency tensor of $G$, respectively. In this paper, we show the perturbation of $\alpha$-spectral radius by contracting an edge. Then we determine the unique unicyclic hypergraph with the maximum $\alpha$-spectral radius among all $r$-uniform unicyclic hypergraphs with fixed diameter. We also determine the unique unicyclic hypergraph with the maximum $\alpha$-spectral radius among all $r$-uniform unicyclic hypergraphs with given number of pendant edges.

The skewness of a graph G, denoted by sk(G), is the minimum number of edges in G whose removal results in a planar graph. It is an important parameter that measures how close a graph is to planarity, and it is complementary, and computationally equivalent, to the Maximum Planar Subgraph Problem. For any connected graph G on p vertices and q edges with girth g, one can easily verify that sk(G) ≥ π(G), where π(G) = ?q - g/(g-2) (p - 2)?, and the graph G is said to be π-skew if equality holds. The concept of π-skew was first proposed by G. L. Chia and C. L. Lee. The π-skew graphs with girth 3 are precisely the graphs that contain a triangulation as a spanning subgraph. The purpose of this paper is to explore the properties of π-skew graphs. Some families of π-skew graphs are obtained by applying these properties, including join of two graphs, complete multipartite graphs and Cartesian product of two graphs. We also discuss the threshold for the existence of a spanning triangulation. Among other results some sufficient conditions regarding the regularity and size of a graph, which ensure a spanning triangulation, are given.