Search

Brown et al. (J Combin Theory Ser B 15(1):77–93, 1973) considered Turán-type extremal problems for digraphs. However, to date there are very few results on this problem, even asymptotically. Let P 2 , 2 → be the orientation of C 4 which consists of two 2-paths with the same initial and terminal vertices. Huang and Lyu [Discrete Math., 343 (5) (2020)] recently determined the Turán number of P 2 , 2 → , and considered it a more natural and interesting problem to determine the Turán number of directed cycles. Let P k → and C k → denote the directed path and the directed cycle of order k, respectively. In this paper we determine the maximum size of C k → -free digraphs of order n for all n , k ∈ N ∗ , as well as the extremal digraphs attaining this maximum size. Similar result is obtained for P k → where n is large. In addition, we generalize the result of Huang and Lyu by characterizing the extremal digraphs avoiding an arbitrary orientation of C 4 except P 2 , 2 → . In particular, for oriented even cycles, we classify which oriented even cycles inherit the difficulty of their underlying graphs and which do not. [ABSTRACT FROM AUTHOR]

In this work, we introduce and study a new graph labelling problem standing as a combination of the 1-2-3 Conjecture and injective colouring of graphs, which also finds connections with the notion of graph irregularity. In this problem, the goal, given a graph G, is to label the edges of G so that every two vertices having a common neighbour get incident to different sums of labels. We are interested in the minimum k such that G admits such a k-labelling. We suspect that almost all graphs G can be labelled this way using labels 1 , ⋯ , Δ (G) . Towards this speculation, we provide bounds on the maximum label value needed in general. In particular, we prove that using labels 1 , ⋯ , Δ (G) is indeed sufficient when G is a tree, a particular cactus, or when its injective chromatic number χ i (G) is equal to Δ (G) . [ABSTRACT FROM AUTHOR]

Let G be a balanced bipartite graph with bipartite sets X, Y. We say that G is Hamilton-biconnected if there is a Hamilton path connecting any vertex in X and any vertex in Y. We define the bipartite independent number α B o (G) to be the maximum integer α such that for any integer partition α = s + t , G has an independent set formed by s vertices in X and t vertices in Y. In this paper we show that if α B o (G) ≤ δ (G) then G is Hamilton-biconnected, unless G has a special construction. [ABSTRACT FROM AUTHOR]

Given a graph G and a positive integer k, the sub-Ramsey number sr(G, k) is defined to be the minimum number m such that every K m whose edges are colored using every color at most k times contains a subgraph isomorphic to G all of whose edges have distinct colors. In this paper, we will concentrate on s r (n K 2 , k) with n K 2 denoting a matching of size n. We first give upper and lower bounds for s r (n K 2 , k) and exact values of s r (n K 2 , k) for some n and k. Afterwards, we show that s r (n K 2 , k) = 2 n when n is sufficiently large and k < n 8 by applying the Local Lemma. [ABSTRACT FROM AUTHOR]

Let $$G_1$$ and $$G_2$$ be two given graphs. The Ramsey number $$R(G_1,G_2)$$ is the least integer r such that for every graph G on r vertices, either G contains a $$G_1$$ or $$\overline{G}$$ contains a $$G_2$$ . A complete bipartite graph $$K_{1,n}$$ is called a star. The kipas $$\widehat{K}_n$$ is the graph obtained from a path of order n by adding a new vertex and joining it to all the vertices of the path. Alternatively, a kipas is a wheel with one edge on the rim deleted. Whereas for star-wheel Ramsey numbers not all exact values are known to date, in contrast we determine all exact values of star-kipas Ramsey numbers. [ABSTRACT FROM AUTHOR]

For a graph G, we denote by $$\nu (G)$$ the order of G, by $$\chi (G)$$ the chromatic number of G and by $$\sigma (G)$$ the minimum size of a color class over all proper $$\chi (G)$$ -colorings of G. For two graphs $$G_1$$ and $$G_2$$ , the Ramsey number $$R(G_1,G_2)$$ is the least integer r such that for every graph G on r vertices, either G contains a $$G_1$$ or $$\overline{G}$$ contains a $$G_2$$ . Suppose that $$G_1$$ is connected. We say that $$G_1$$ is $$G_2$$ -good if $$R(G_1,G_2)=(\chi (G_2)-1)(\nu (G_1)-1)+\sigma (G_2)$$ . In this note, we obtain a condition for graphs H such that a path is H-good. [ABSTRACT FROM AUTHOR]

A graph G is called claw-o-heavy if every induced claw ( $$K_{1,3}$$ ) of G has two end-vertices with degree sum at least | V( G)|. For a given graph S, G is called S-f-heavy if for every induced subgraph H of G isomorphic to S and every pair of vertices $$u,v\in V(H)$$ with $$d_H(u,v)=2,$$ there holds $$\max \{d(u),d(v)\}\ge |V(G)|/2.$$ In this paper, we prove that every 2-connected claw- o-heavy and $$Z_3$$ - f-heavy graph is hamiltonian (with two exceptional graphs), where $$Z_3$$ is the graph obtained by identifying one end-vertex of $$P_4$$ (a path with 4 vertices) with one vertex of a triangle. This result gives a positive answer to a problem proposed Ning and Zhang (Discrete Math 313:1715-1725, ), and also implies two previous theorems of Faudree et al. and Chen et al., respectively. [ABSTRACT FROM AUTHOR]

For two given graphs $$G_1$$ and $$G_2$$ , the Ramsey number $$R(G_1,G_2)$$ is the least integer r such that for every graph G on r vertices, either G contains a $$G_1$$ or $$\overline{G}$$ contains a $$G_2$$ . In this note, we determined the Ramsey number $$R(K_{1,n},W_m)$$ for even m with $$n+2\le m\le 2n-2$$ , where $$W_m$$ is the wheel on $$m+1$$ vertices, i.e., the graph obtained from a cycle $$C_m$$ by adding a vertex v adjacent to all vertices of the $$C_m$$ . [ABSTRACT FROM AUTHOR]

Let $$G$$ be a $$k$$ -connected graph with $$k\ge 2$$ . In this paper we first prove that: For two distinct vertices $$x$$ and $$z$$ in $$G$$ , it contains a path connecting $$x$$ and $$z$$ which passes through its any $$k-2$$ specified vertices with length at least the average degree of the vertices other than $$x$$ and $$z$$ . Further, with this result, we prove that: If $$G$$ has $$n$$ vertices and $$m$$ edges, then it contains a cycle of length at least $$2m/(n-1)$$ passing through its any $$k-1$$ specified vertices. Our results generalize a theorem of Fan on the existence of long paths and a classical theorem of Erdős and Gallai on the existence of long cycles under the average degree condition. [ABSTRACT FROM AUTHOR]

Earlier results originating from Bedrossian's PhD Thesis focus on characterizing pairs of forbidden subgraphs that imply hamiltonian properties. Instead of forbidding certain induced subgraphs, here we relax the requirements by imposing Ore-type degree conditions on the induced subgraphs. In particular, adopting the terminology introduced by Čada, for a graph $$G$$ on $$n$$ vertices and a fixed graph $$H$$ , we say that $$G$$ is $$H$$ - $$o_1$$ -heavy if every induced subgraph of $$G$$ isomorphic to $$H$$ contains two nonadjacent vertices with degree sum at least $$n+1$$ in $$G$$ . For a family $${\mathcal {H}}$$ of graphs, $$G$$ is called $${\mathcal {H}}$$ - $$o_{1}$$ -heavy if $$G$$ is $$H$$ - $$o_1$$ -heavy for every $$H\in \mathcal {H}$$ . In this paper we characterize all connected graphs $$R$$ and $$S$$ other than $$P_3$$ (the path on three vertices) such that every 2-connected $$\{R,S\}$$ - $$o_1$$ -heavy graph is either a cycle or pancyclic, thereby extending previous results on forbidden subgraph conditions for pancyclicity and on heavy subgraph conditions for hamiltonicity. [ABSTRACT FROM AUTHOR]