Search

Bondy and Vince showed that every graph with minimum degree at least three contains two cycles of lengths differing by one or two. We prove the following average degree counterpart that every n $n$‐vertex graph G $G$ with at least 52(n−1) $\frac{5}{2}(n-1)$ edges, unless 4|(n−1) $4|(n-1)$ and every block of G $G$ is a clique K5 ${K}_{5}$, contains two cycles of consecutive even lengths. Our proof is mainly based on structural analysis, and a crucial step which may be of independent interest shows that the same conclusion holds for every 3‐connected graph with at least six vertices. This solves a special case of a conjecture of Verstraëte. The quantitative bound is tight and also provides the optimal extremal number for cycles of length two modulo four. [ABSTRACT FROM AUTHOR]

As the counterpart of classical theorems on cycles of consecutive lengths due to Bondy and Bollobás in spectral graph theory, Nikiforov proposed the following open problem in 2008: What is the maximum C $C$ such that for all positive ε⌊n24⌋ $\rho (G)\gt \sqrt{\lfloor \frac{{n}^{2}}{4}\rfloor }$ contains a cycle of length ℓ $\ell $ for each integer ℓ∈[3,(C−ε)n] $\ell \in [3,(C-\varepsilon)n]$. We prove that C≥14 $C\ge \frac{1}{4}$, improving the existing bounds. Besides several novel ideas, our proof technique is partly inspired by the recent research on Ramsey numbers of star versus large even cycles due to Allen, Łuczak, Polcyn, and Zhang, and with aid of a powerful spectral inequality. We also derive an Erdős–Gallai‐type edge number condition for even cycles, which may be of independent interest. [ABSTRACT FROM AUTHOR]

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]

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]

For positive integers n > d ≥ k , let ϕ (n , d , k) denote the least integer ϕ such that every n -vertex graph with at least ϕ vertices of degree at least d contains a path on k + 1 vertices. Many years ago, Erdős, Faudree, Schelp and Simonovits proposed the study of the function ϕ (n , d , k) , and conjectured that for any positive integers n > d ≥ k , it holds that ϕ (n , d , k) ≤ ⌊ k − 1 2 ⌋ ⌊ n d + 1 ⌋ + ϵ , where ϵ = 1 if k is odd and ϵ = 2 otherwise. In this paper we determine the values of the function ϕ (n , d , k) exactly. This confirms the above conjecture of Erdős et al. for all positive integers k ≠ 4 and in a corrected form for the case k = 4. Our proof utilizes, among others, a lemma of Erdős et al. [3] , a theorem of Jackson [6] , and a (slight) extension of a very recent theorem of Kostochka, Luo and Zirlin [7] , where the latter two results concern maximum cycles in bipartite graphs. Moreover, we construct examples to provide answers to two closely related questions raised by Erdős et al. [ABSTRACT FROM AUTHOR]

The bipartite Turán number, denoted by ex(m,n,H), is the maximum number of edges in an H‐free bipartite graph with two parts of sizes m and n, respectively. In this article, we prove ex(m,n,C2t)=(t−1)n+m−t+1 for any positive integers m,n,t with n≥m≥t≥m2+1, which confirms (in a strong form) the unsolved case of a conjecture of Győri. Let G=(X,Y;E) be a bipartite graph with ∣X∣=n and ∣Y∣=m. Suppose that n≥m≥2k+2 for some k∈N. We prove that G contains cycles of all even lengths from 4 to 2m−2k if e(G)≥(m−k−1)n+k+2. This result sharpens a theorem on long cycles in bipartite graphs due to Jackson. As a main tool, for a longest cycle C in a bipartite graph, we prove an upper bound of the number of edges which are incident with at most one vertex in C, which is a bipartite analogue of a classical theorem of Bondy. Our proof technique is structural. [ABSTRACT FROM AUTHOR]

Let H be a set of graphs. A graph G is said to be H -free if G does not contain H as an induced subgraph for all H ∈ H , and we call H a forbidden pair if | H | = 2. A graph is called supereulerian if it contains a spanning connected even subgraph. In 1979, Pulleyblank showed that determining whether a graph is supereulerian, even when restricted to planar graphs, is NP-complete. In this paper, we characterize all pairs of graphs R , S (not necessary connected) such that every 2-connected or 2-edge-connected { R , S } -free graph (of sufficiently large order) is supereulerian. We also characterize all minimal 2-connected non-supereulerian graphs, which extends a result by the third author and Xiong (2017) [29]. [ABSTRACT FROM AUTHOR]

For a 2-connected graph G on n vertices and two vertices x , y ∈ V (G) , we prove that there is an (x , y) -path of length at least k , if there are at least n − 1 2 vertices in V (G) \ { x , y } of degree at least k. This strengthens a celebrated theorem due to Erdős and Gallai in 1959. As the first application of this result, we show that a 2-connected graph with n vertices contains a cycle of length at least 2 k , if it has at least n 2 + k vertices of degree at least k. This confirms a 1975 conjecture made by Woodall. As other applications, we obtain some results which generalize previous theorems of Dirac, Erdős-Gallai, Bondy, and Fujisawa et al., present short proofs of the path case of Loebl-Komlós-Sós Conjecture which was verified by Bazgan et al. and a conjecture of Bondy on longest cycles (for large graphs) which was confirmed by Fraisse and Fournier, and make progress on a conjecture of Bermond. [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]

A properly colored walk in an edge-colored graph is a walk such that consecutive edges are of distinct colors. In this paper, based on a transformation from directed graphs to edge-colored graphs, we classified edge-colored graphs into three families: degenerate edge-colored graphs, semi-degenerate edge-colored graphs and non-degenerate graphs. By a polynomial-time computable parameter related to properly colored walks, we gave a characterization of these three families. Applying this characterization, we slightly strengthened Yeo's Theorem (Every edge-colored graph G containing no PC cycle contains a vertex z ∈ V (G) such that each component of G − z is joint to z with at most one color , Yeo, 1997). [ABSTRACT FROM AUTHOR]

For an arc-colored digraph D , define its kernel by rainbow paths to be a set S of vertices such that (i) no two vertices of S are connected by a rainbow path in D , and (ii) every vertex outside S can reach S by a rainbow path in D. In this paper, we first show that it is NP-complete to decide whether an arc-colored tournament has a kernel by rainbow paths, where a tournament is an orientation of a complete graph. In addition, we show that every arc-colored n -vertex tournament with all its strongly connected k -vertex subtournaments, 3 ⩽ k ⩽ n , colored with at least k − 1 colors has a kernel by rainbow paths. [ABSTRACT FROM AUTHOR]

In 1962, Erdős proved that if a graph G with n vertices satisfies e ( G ) > max n − k 2 + k 2 , ⌈ ( n + 1 ) ∕ 2 ⌉ 2 + n − 1 2 2 , where the minimum degree δ ( G ) ≥ k and 1 ≤ k ≤ ( n − 1 ) ∕ 2 , then it is Hamiltonian. For n ≥ 2 k + 1 , let E n k = K k ∨ ( k K 1 + K n − 2 k ) , where “ ∨ ” is the “join” operation. One can observe e ( E n k ) = n − k 2 + k 2 and E n k is not Hamiltonian. As E n k contains induced claws for k ≥ 2 , a natural question is to characterize all 2-connected claw-free non-Hamiltonian graphs with the largest possible number of edges. We answer this question completely by proving a claw-free analog of Erdős’ theorem. Moreover, as byproducts, we establish several tight spectral conditions for a 2-connected claw-free graph to be Hamiltonian. Similar results for the traceability of connected claw-free graphs are also obtained. Our tools include Ryjáček’s claw-free closure theory and Brousek’s characterization of minimal 2-connected claw-free non-Hamiltonian graphs. [ABSTRACT FROM AUTHOR]

A closed curve in the Freudenthal compactification | G | of an infinite locally finite graph G is called a Hamiltonian curve if it meets every vertex of G exactly once (and hence it meets every end at least once). We prove that | G | has a Hamiltonian curve if and only if every finite vertex set of G is contained in a cycle of G . We apply this to extend a number of results and conjectures on finite graphs to Hamiltonian curves in infinite locally finite graphs. For example, Barnette’s conjecture (that every finite planar cubic 3 -connected bipartite graph is Hamiltonian) is equivalent to the statement that every one-ended planar cubic 3 -connected bipartite graph has a Hamiltonian curve. It is also equivalent to the statement that every planar cubic 3 -connected bipartite graph with a nowhere-zero 3 -flow (with no restriction on the number of ends) has a Hamiltonian curve. However, there are 7 -ended planar cubic 3 -connected bipartite graphs that do not have a Hamiltonian curve. [ABSTRACT FROM AUTHOR]

Let H be a class of given graphs. A graph G is said to be H -free if G contains no induced copies of H for every H ∈ H . A graph is called traceable if it contains a Hamilton path. Faudree and Gould (1997) characterized all the pairs { R , S } of connected subgraphs such that every connected { R , S } -free graph is traceable. Li and Vrána (2016) first consider the disconnected forbidden subgraphs, and characterized all pairs of disconnected forbidden subgraphs for hamiltonicity. In this article, we characterize all pairs { R , S } of graphs such that there exists an integer n 0 such that every connected { R , S } -free graph of order at least n 0 is traceable. [ABSTRACT FROM AUTHOR]

Let H be a given graph. A graph G is said to be H-free if G contains no induced copies of H. For a class [ABSTRACT FROM AUTHOR]

In 1962, Erdős proved a theorem on the existence of Hamilton cycles in graphs with given minimum degree and number of edges. Significantly strengthening in case of balanced bipartite graphs, Moon and Moser proved a corresponding theorem in 1963. In this paper we establish several spectral analogues of Moon and Moser's theorem on Hamilton paths in balanced bipartite graphs and nearly balanced bipartite graphs. One main ingredient of our proofs is a structural result of its own interest, involving Hamilton paths in balanced bipartite graphs with given minimum degree and number of edges. [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]

Let k , ℓ be two positive integers. An S k , ℓ is a graph obtained from disjoint K 1 , k and K 1 , ℓ by adding an edge between the k -degree vertex in K 1 , k and the ℓ -degree vertex in K 1 , ℓ. An S k , ℓ -free graph is a graph containing no induced subgraph isomorphic to S k , ℓ. In this paper, we show that, for any two positive integers k , ℓ with 2 ⩽ k ⩽ ℓ , there exists a constant c = c (k , ℓ) such that every connected balanced S k , ℓ -free bipartite graph with minimum degree at least c contains a connected k -factor. [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]

In 1962, Erdős gave a sufficient condition for Hamilton cycles in terms of the vertex number, edge number and minimum degree of graphs which generalized Ore’s theorem. One year later, Moon and Moser gave an analogous result for Hamilton cycles in balanced bipartite graphs. In this paper, we present the spectral analogues of Erdős’ theorem and Moon–Moser’s theorem, respectively. Letbe the class of non-Hamiltonian graphs of ordernand minimum degree at leastk. We determine the maximum (signless Laplacian) spectral radius of graphs in(for large enoughn), and the minimum (signless Laplacian) spectral radius of the complements of graphs in. All extremal graphs with the maximum (signless Laplacian) spectral radius and with the minimum (signless Laplacian) spectral radius of the complements are determined, respectively. We also solve similar problems for balanced bipartite graphs and the quasi-complements. [ABSTRACT FROM PUBLISHER]

Let G be a graph and let diam( G ) denote the diameter of G . The distance power G N of G is the undirected graph with vertex set V ( G ), in which x and y are adjacent if their distance d ( x, y ) in G belongs to N , where N is a non-empty subset of { 1 , 2 , … , diam ( G ) } . The unitary Cayley graph is the graph having the vertex set Z n and the edge set { ( a , b ) : a , b ∈ Z n , gcd ( a − b , n ) = 1 } . In this paper, we determine the energies of distance powers of unitary Cayley graphs, and classify all Ramanujan distance powers of unitary Cayley graphs. By the energies of distance powers of unitary Cayley graphs, we construct infinitely many pairs of non-cospectral equienergetic graphs. Moreover, we characterize all hyperenergetic distance powers of unitary Cayley graphs. [ABSTRACT FROM AUTHOR]

In this paper, we consider the least integer d such that every longest cycle of a k-connected graph of order n (and of independent number α) contains all vertices of degree at least d. [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]

Let G be a graph. For a given graph H , we say that G is H - free if G contains no copies of H as an induced subgraph. Suppose that G is 2-connected, has n vertices, and α is a real number with 0 ≤ α ≤ 1 . In this paper, we characterize the connected graphs R such that G being R -free implies that every longest cycle of G passes through all vertices with degree at least α n + O ( 1 ) in G . [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]

Let G1 and G2 be two given graphs. The Ramsey number R(G1,G2) is the least integer r such that for every graph G on r vertices, either G contains a G1 or Ḡ contains a G2. Parsons gave a recursive formula to determine the values of R(Pn,K1,m), where Pn is a path on n vertices and K1,m is a star on m+1 vertices. In this note, we study the Ramsey numbers R(Pn,K1,m), where Pn is a linear forest on m vertices. We determine the exact values of R(Pn,K1∨Fm) for the cases m ≤ n and m ≥ 2n, and for the case that Fm has no odd component. Moreover, we give a lower bound and an upper bound for the case n+1 ≤ m ≤ 2n−1 and Fm has at least one odd component. [ABSTRACT FROM AUTHOR]

An arc u v of a digraph D is called universal if u v and w are in a common cycle for any vertex w of D . We show that every arc of a tournament T is universal if and only if T is either 2-connected or has a cut-vertex v such that the in- and out-neighbors of v both induce strongly connected subtournaments. [ABSTRACT FROM AUTHOR]

Abstract: Let be an edge-colored graph. The color degree of a vertex of , is defined as the number of colors of the edges incident to . The color number of is defined as the number of colors of the edges in . A rainbow triangle is one in which every pair of edges have distinct colors. In this paper we give some sufficient conditions for the existence of rainbow triangles in edge-colored graphs in terms of color degree, color number and edge number. As a corollary, a conjecture proposed by Li and Wang [H. Li and G. Wang, Color degree and heterochromatic cycles in edge-colored graphs, European J. Combin. 33 (2012) 1958–1964] is confirmed. [Copyright &y& Elsevier]

Abstract: A graph is called homogeneously traceable if for every vertex of , contains a Hamilton path starting from . For a graph , we say that is -free if contains no induced subgraph isomorphic to . For a family of graphs, is called -free if is -free for every . Determining families of graphs such that every -free graph has some graph property has been a popular research topic for several decades, especially for Hamiltonian properties, and more recently for properties related to the existence of graph factors. In this paper we give a complete characterization of all pairs of connected graphs such that every 2-connected -free graph is homogeneously traceable. [Copyright &y& Elsevier]

Abstract: For nonnegative integers and , let denote the family of digraphs in which every vertex has either indegree at most or outdegree at most . In this paper we prove that the edges of every digraph in and can be covered by at most five directed cuts and present an example in showing that this result is best possible. [Copyright &y& Elsevier]

Abstract: Bollobás and Scott proved that if the weighted outdegree of every vertex of an edge-weighted digraph is at least 1, then the digraph contains a (directed) path of weight at least 1. In this note we characterize the extremal weighted digraphs with no heavy paths. Our result extends a corresponding theorem of Bondy and Fan on weighted graphs. We also give examples to show that a result of Bondy and Fan on the existence of heavy paths connecting two given vertices in a 2-connected weighted graph does not extend to 2-connected weighted digraphs. [Copyright &y& Elsevier]

Let t 1 , … , t r ∈ [ 4 , 2 q ] be any r even integers, where q ≥ 2 and r ≥ 1 are two integers. In this note, we show that every bipartite tournament with minimum outdegree at least q r − 1 contains r vertex-disjoint directed cycles of lengths t 1 ′ , … , t r ′ such that t i ′ = t i for t i = 0 ( mod 4 ) and t i ′ ∈ { t i , t i + 2 } for t i = 2 ( mod 4 ) , where 1 ≤ i ≤ r . The special case q = 2 of the result verifies the bipartite tournament case of a conjecture proposed by Bermond and Thomassen, stating that every digraph with minimum outdegree at least 2 r − 1 contains at least r vertex-disjoint directed cycles. [ABSTRACT FROM AUTHOR]

Abstract: A weighted digraph is a digraph such that every arc is assigned a nonnegative number, called the weight of the arc. The weighted outdegree of a vertex in a weighted digraph is the sum of the weights of the arcs with as their tail, and the weight of a directed cycle in is the sum of the weights of the arcs of . In this note we prove that if every vertex of a weighted digraph with order has weighted outdegree at least 1, then there exists a directed cycle in with weight at least . This proves a conjecture of Bollobás and Scott up to a constant factor. [Copyright &y& Elsevier]

Abstract: Let be a 2-connected weighted graph and an integer. In this note we prove that if the sum of the weighted degrees of every pairwise nonadjacent vertices is at least , then contains either a cycle of weight at least or a spanning tree with no more than leaves. [Copyright &y& Elsevier]

A spanning circuit in a graph is defined as a closed trail visiting each vertex of the graph. A compatible spanning circuit in an edge-colored graph refers to a spanning circuit in which each pair of edges traversed consecutively along the spanning circuit has distinct colors. As two extreme cases, sufficient conditions for the existence of compatible Hamilton cycles and compatible Euler tours have been obtained in previous literature. In this paper, we first establish sufficient conditions for the existence of compatible spanning circuits visiting each vertex exactly k times, for every feasible integer k , in edge-colored complete graphs and complete equipartition r -partite graphs. We also provide sufficient conditions for the existence of compatible spanning circuits visiting each vertex v at least ⌊ (d (v) − 1) ∕ 2 ⌋ times in edge-colored graphs satisfying Ore-type degree conditions. [ABSTRACT FROM AUTHOR]

Let G be an edge-colored complete graph on n vertices such that there exist at least n distinct colors on edges incident to every pair of its vertices. In this paper, we first show that every edge of G with n ≥ 6 k − 19 is contained in a properly colored cycle of length k. Further, we prove that if G contains no monochromatic triangles, then there exists a properly colored path of length l for every 1 ≤ l ≤ n − 1 between each pair of vertices of G and every vertex of G is contained in a properly colored cycle of length k for any 3 ≤ k ≤ n. [ABSTRACT FROM AUTHOR]

We present new sharp sufficient conditions for the existence of properly colored and rainbow C4 ${C}_{4}$'s in edge‐colored graphs. Our first results deal with sharp color neighborhood conditions for the existence of properly colored C4 ${C}_{4}$'s in edge‐colored complete graphs and complete bipartite graphs, respectively. Next, we characterize the extremal graphs for an anti‐Ramsey number result due to Alon on the existence of rainbow C4 ${C}_{4}$'s in edge‐colored complete graphs. We also generalize Alon's result from complete to general edge‐colored graphs. Finally, we derive a structural property regarding the extremal graphs for a bipartite counterpart of Alon's result due to Axenovich, Jiang, and Kündgen on the existence of rainbow C4 ${C}_{4}$'s in edge‐colored complete bipartite graphs. We also generalize their result from complete to general bipartite edge‐colored graphs. [ABSTRACT FROM AUTHOR]

The 1–2–3 Conjecture asserts that, for every connected graph different from K 2 , its edges can be labeled with 1 , 2 , 3 so that, when coloring each vertex with the sum of its incident labels, no two adjacent vertices get the same color. This conjecture takes place in the more general context of distinguishing labelings, where the goal is to label graphs so that some pairs of their elements are distinguishable relatively to some parameter computed from the labeling. In this work, we investigate the consequences of labeling graphs as in the 1–2–3 Conjecture when it is further required to make the maximum resulting color as small as possible. In some sense, we aim at producing a number of colors that is as close as possible to the chromatic number of the graph. We first investigate the hardness of determining the minimum maximum color by a labeling for a given graph, which we show is NP -complete in the class of bipartite graphs but polynomial-time solvable in the class of graphs with bounded treewidth. We then provide bounds on the minimum maximum color that can be generated both in the general context, and for particular classes of graphs. Finally, we study how using larger labels permit to reduce the maximum color. [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]

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]

An edge-colored graph is called rainbow if all the colors on its edges are distinct. Given a positive integer n and a graph G , the anti-Ramsey number a r (n , G) is the maximum number of colors in an edge-coloring of K n with no rainbow copy of G. Denote by k C 3 the union of k vertex-disjoint copies of C 3. In this paper, we determine the anti-Ramsey number a r (n , k C 3) for n = 3 k and n ≥ 2 k 2 − k + 2 , respectively. When 3 k ≤ n ≤ 2 k 2 − k + 2 , we give lower and upper bounds for a r (n , k C 3). [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]

A subgraph of an edge-colored graph is rainbow, if all of its edges have different colors. For a graph G and a family H of graphs, the anti-Ramsey number ar (G , H) is the maximum number k such that there exists an edge-coloring of G with exactly k colors without rainbow copy of any graph in H. In this paper, we study the anti-Ramsey numbers of C 3 and C 4 in complete r -partite graphs. For r ≥ 3 and n 1 ≥ n 2 ≥ ⋯ ≥ n r ≥ 1 , we determine ar (K n 1 , n 2 , ... , n r , { C 3 , C 4 }) , ar (K n 1 , n 2 , ... , n r , C 3) and ar (K n 1 , n 2 , ... , n r , C 4). [ABSTRACT FROM AUTHOR]

Let G be a (not necessarily properly) edge-colored graph. A compatible spanning circuit in G is a closed trail containing all vertices of G in which any two consecutively traversed edges have distinct colors. As two extremal cases, the existence of compatible (i.e., properly edge-colored) Hamilton cycles and compatible Euler tours have been studied extensively. More recently, sufficient conditions for the existence of compatible spanning circuits visiting each vertex v of G at least ⌊ (d (v) − 1) ∕ 2 ⌋ times in graphs satisfying Ore-type degree conditions have been established. In this paper, we continue the research on sufficient conditions for the existence of compatible spanning circuits visiting each vertex at least a specified number of times. We respectively consider graphs satisfying Fan-type degree conditions, graphs with a high edge-connectivity, and the asymptotical existence of such compatible spanning circuits in random graphs. [ABSTRACT FROM AUTHOR]

In the theory and applications of graphs, it is a basic problem to compute the numbers of independent sets and matchings of given sizes. Since the problem of computing the total number of independent sets and that of matchings of graphs is #P-complete, it is unlikely to give efficient algorithms to find the numbers of independent sets and matchings of given sizes. In this paper, for graphs with order n and treewidth at most p , we present two dynamic algorithms to compute the numbers of independent sets of all sizes with runtime O (2 p  ·  pn 3 ) and the numbers of matchings of all sizes with runtime O (2 2 p  ·  pn 3 ), respectively. By the algorithms presented in this paper, for graphs with small treewidths, the numbers of independent sets and matchings of all possible sizes can be computed efficiently. [ABSTRACT FROM AUTHOR]

Let G be a digraph and L G be its line digraph. Levine gave a formula that relates the number of rooted spanning trees of L G and that of G , with the restriction that G has no sources. In this note, we show that this restriction can be removed, thus his formula holds for all digraphs. [ABSTRACT FROM AUTHOR]