Search

Given a graph H and a positive integer n, the Turán number of H of the order n, denoted by ex(n, H), is the maximum size of a simple graph of order n that does not contain H as a subgraph. Given graphs G and H, G ∨ H denotes the join of G and H. In this paper, we prove e x (n , K m ∨ C 2 k - 1) = (m + 1) n 2 2 (m + 2) for n ≥ 2 (m + 2) k - 3 (m + 2) - 1 . [ABSTRACT FROM AUTHOR]

Let G be a graph. For two positive integers d and h, a (d, h)-decomposition of G is a pair (G, H) such that H is a subgraph of G of maximum degree at most h and D is an acyclic orientation of G - E (H) of maximum out-degree at most d. A graph G is (d, h)-decomposable if G has a (d, h)-decomposition. In this paper, we prove that every planar graph without intersecting 3-cycles and adjacent 4 - -cycles is (2, 1)-decomposable. As a corollary, we obtain that every planar graph without intersecting 3-cycles and adjacent 4 - -cycles has a matching M such that G - M is 2-degenerate and hence G - M is DP-3-colorable and Alon-Tarsi number of G - M is at most 3. [ABSTRACT FROM AUTHOR]

A graph G of order n is said to be k-factor-critical for integers 1 ≤ k < n , if the removal of any k vertices results in a graph with a perfect matching. 1- and 2-factor-critical graphs are the well-known factor-critical and bicritical graphs, respectively. A k-factor-critical graph G is called minimal if for any edge e ∈ E (G) , G - e is not k-factor-critical. In 1998, O. Favaron and M. Shi conjectured that every minimally k-factor-critical graph of order n has the minimum degree k + 1 and confirmed it for k = 1 , n - 2 , n - 4 and n - 6 . In this paper, we use a simple method to reprove the above results. As a main result, the further use of this method enables us to prove the conjecture to be true for k = n - 8 . We also obtain that every minimally (n - 6) -factor-critical graph of order n has at most n - Δ (G) vertices with the maximum degree Δ (G) for Δ (G) ≥ n - 4 . [ABSTRACT FROM AUTHOR]

Given two non-empty graphs G, H and a positive integer k, the Gallai–Ramsey number gr k (G : H) is defined as the minimum integer N such that for all n ≥ N , every k-edge-coloring of K n contains either a rainbow colored copy of G or a monochromatic copy of H. In this paper, we got some exact values or bounds for gr k (P 5 : H) (k ≥ 3) if H is a general graph or a star with extra independent edges or a pineapple. [ABSTRACT FROM AUTHOR]

Let G be a graph and k a positive integer. A strong k-edge-coloring of G is a mapping ϕ : E (G) → { 1 , 2 , ⋯ , k } such that for any two edges e and e ′ that are either adjacent to each other or adjacent to a common edge, ϕ (e) ≠ ϕ (e ′) . The strong chromatic index of G, denoted as χ s ′ (G) , is the minimum integer k such that G has a strong k-edge-coloring. Lv, Li and Zhang [Graphs and Combinatorics 38 (3) (2022) 63] proved that if G is a claw-free subcubic graph other than the triangular prism then χ s ′ (G) ≤ 8 . In addition, they asked if the upper bound 8 can be improved to 7. In this paper, we answer this question in the affirmative. Our proof implies a polynomial-time algorithm for finding strong 7-edge-colorings of such graphs. We also construct infinitely many claw-free subcubic graphs with their strong chromatic indices attaining the bound 7. [ABSTRACT FROM AUTHOR]

Let n, k, t be positive integers. What is the maximum number of arcs in a digraph on n vertices in which there are at most t distinct walks of length k with the same endpoints? Denote f (t) = max { 2 t + 1 , 2 2 t + 9 / 4 + 1 / 2 + 3 } . In this paper, we prove that the maximum number is equal to n (n - 1) / 2 and the extremal digraph are the transitive tournaments when k ≥ n - 1 ≥ f (t) . Based on this result, we may determine the maximum numbers and the extremal digraphs when k ≥ f (t) and n is sufficiently large, which generalizes the existing results. A conjecture is also presented. [ABSTRACT FROM AUTHOR]

Graph labeling is a well-known and intensively investigated problem in graph theory. Sparse anti-magic squares are useful in constructing vertex-magic labeling for graphs. For positive integers n and d with d < n , an n × n array A based on { 0 , 1 , ... , n d } is called a sparse anti-magic square of ordernwith densityd, denoted by SAMS(n, d), if each element of { 1 , 2 , ... , n d } occurs exactly one entry of A, and its row-sums, column-sums and two main diagonal-sums constitute a set of 2 n + 2 consecutive integers. An SAMS(n, d) is called regular if there are exactly d non-zero elements (or positive entries) in each row, each column and each main diagonal. In this paper, we investigate the existence of regular sparse anti-magic squares of odd order, and it is proved that for any odd n, there exists a regular SAMS(n, d) if and only if 2 ≤ d ≤ n - 1 . [ABSTRACT FROM AUTHOR]

Graphs considered in this paper are finite, undirected and without loops, but with multiple edges. For an integer t ≥ 1 , denote by MG t the class of graphs whose maximum multiplicity is at most t. A graph G is called strictly t-degenerate if every non-empty subgraph H of G contains a vertex v whose degree in H is at most t - 1 . The point partition number χ t (G) of G is the smallest number of colors needed to color the vertices of G so that each vertex receives a color and vertices with the same color induce a strictly t-degenerate subgraph of G. So χ 1 is the chromatic number, and χ 2 is known as the point aboricity. The point partition number χ t with t ≥ 1 was introduced by Lick and White (Can J Math 22:1082–1096, 1970). If H is a simple graph, then tH denotes the graph obtained from H by replacing each edge of H by t parallel edges. Then ω t (G) is the largest integer n such that G contains a t K n as a subgraph. Let G be a graph belonging to MG t . Then ω t (G) ≤ χ t (G) and we say that G is χ t -perfect if every induced subgraph H of G satisfies ω t (H) = χ t (H) . Based on the Strong Perfect Graph Theorem due to Chudnowsky, Robertson, Seymour and Thomas (Ann Math 164:51–229, 2006), we give a characterization of χ t -perfect graphs of MG t by a set of forbidden induced subgraphs (see Theorems 2 and 3). We also discuss some complexity problems for the class of χ t -critical graphs. [ABSTRACT FROM AUTHOR]

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. Much like graph Ramsey numbers, Gallai-Ramsey numbers have gained a reputation as being very difficult to compute in general. As yet, still only precious few sharp results are known. In this paper, we obtain bounds on the Gallai-Ramsey number for wheels and the exact value for the wheel on 5 vertices. [ABSTRACT FROM AUTHOR]

A one-factorization F of the complete graph K n is ( l , C k ), where l ≥ 0 and k ≥ 4 are integers, if the union F ∪ G , for any F , G ∈ F , includes exactly l (edge-disjoint) cycles of length k ( l k ≤ n ). Moreover, a pair of orthogonal one-factorizations F and G of the complete graph K n is ( l , C k ) if the union F ∪ G , for any F ∈ F and G ∈ G , includes exactly l cycles of length k. In this paper, we prove the following: if q ≡ 11 (mod 24) is an odd prime power, then there is a ( 1 , C 4 ) one-factorization of K q + 1 . Also, there is a pair of orthogonal ( 2 , C 4 ) one-factorization of K q + 1 . [ABSTRACT FROM AUTHOR]

Let G be a graph and P be a property of graphs. A subset S ⊆ V (G) is called a P -admissible set of G if G - N [ S ] admits the property P . The P -admission number of G, denoted by η (G , P) , is the cardinality of a minimum P -admissible set in G. For a positive integer k, we say a graph G has the property R k if the radius of each component of G is at most k. In particular, η (G , R 1) is the cardinality of a smallest set S such that each component of G - N [ S ] has a universal vertex. In this paper, we establish sharp upper bound for η (G , R 1) for a connected graph G. We show that for a connected graph G ≠ C 7 of order n, η (G , R 1) ≤ n 4 . The bound is sharp. Several related problems are proposed. [ABSTRACT FROM AUTHOR]

An inclusive distance vertex irregular labeling of a graph G is an assignment of positive integers { 1 , 2 , ... , k } to the vertices of G such that for every vertex the sum of numbers assigned to its closed neighborhood is different. The minimum number k for which exists an inclusive distance vertex irregular labeling of G is denoted by dis ^ (G) . In this paper we prove that for a simple graph G on n vertices in which no two vertices have the same closed neighborhood dis ^ (G) ≤ n 2 . [ABSTRACT FROM AUTHOR]

Let G be a graph and k an integer with 2 ≤ k ≤ n . The k-tree-connectivity of G, denoted by κ k (G) , is defined as the minimum κ G (S) over all k-subsets S of vertices, where κ G (S) denotes the maximum number of internally disjoint S-trees in G. The k-path-connectivity of G, denoted by π k (G) , is defined as the minimum π G (S) over all k-subsets S of vertices, where π G (S) denotes the maximum number of internally disjoint S-paths in G. In this paper, we first prove that for any fixed integer k ≥ 1 , given a graph G and a subset S of V(G), deciding whether π G (S) ≥ k is NP -complete. Moreover, we also show that for any fixed integer k 1 ≥ 5 , given a graph G, a k 1 -subset S of V(G) and an integer 1 ≤ k 2 ≤ n - 1 , deciding whether π G (S) ≥ k 2 is NP -complete. Let π (k , ℓ) = 1 + max { κ (G) | G \ is\ a\ graph\ with π k (G) < ℓ } . Hager (Discrete Math 59:53–59, 1986) showed that ℓ (k - 1) ≤ π (k , ℓ) ≤ 2 k - 2 ℓ and conjectured that π (k , ℓ) = ℓ (k - 1) for k ≥ 2 and ℓ ≥ 1 . He also confirmed the conjecture for 2 ≤ k ≤ 4 and proved π (5 , ℓ) ≤ ⌈ 9 2 ℓ ⌉ . By introducing a "Generalized Path-Bundle Transformation", we confirm the conjecture for k = 5 and prove that π (k , ℓ) ≤ 2 k - 3 ℓ for k ≥ 5 and ℓ ≥ 1 . By employing this transformation, we also prove that if G is a graph with κ (G) ≥ (k - 1) ℓ for any k ≥ 2 and ℓ ≥ 1 , then κ k (G) ≥ ℓ . [ABSTRACT FROM AUTHOR]

For any given integer r ⩾ 3 , let k = k (n) be an integer with r ⩽ k ⩽ n . A hypergraph is r-uniform if each edge is a set of r vertices, and is said to be linear if two edges intersect in at most one vertex. Let A 1 , ... , A k be a given k-partition of [n] with | A i | = n i ⩾ 1 . An r-uniform hypergraph H is called k-partite if each edge e satisfies | e ∩ A i | ⩽ 1 for 1 ⩽ i ⩽ k . In this paper, the number of linear k-partite r-uniform hypergraphs on n → ∞ vertices is determined asymptotically when the number of edges is m (n) = o (n 4 3) . For k = n , it is the number of linear r-uniform hypergraphs on vertex set [n] with m = o (n 4 3) edges. [ABSTRACT FROM AUTHOR]

For two graphs G 1 and G 2 , the star-critical Ramsey number r ∗ (G 1 , G 2) is the minimum integer k such that any red/blue edge-coloring of K r - 1 ⊔ K 1 , k contains a red copy of G 1 or a blue copy of G 2 , where r is the classical Ramsey number R (G 1 , G 2) and K r - 1 ⊔ K 1 , k is the graph obtained from a K r - 1 and an additional vertex v by joining v to k vertices of K r - 1 . Let C n denote a cycle of order n and W m a wheel of order m + 1 . Hook (2010) proved that r ∗ (C n , W 3) = 2 n for n ≥ 5 . In this paper, it is shown that r ∗ (C n , W m) = 2 n for m odd, n ≥ m ≥ 5 and n ≥ 60 . [ABSTRACT FROM AUTHOR]

The Turán number ex(n, H) is the maximum number of edges in any graph of order n that contains no copy of H as a subgraph. For any three positive integers p, q, r with p ≤ q ≤ r and q ≥ 2 , let θ (p , q , r) denote the graph obtained from three internally disjoint paths with the same pair of endpoints, where the three paths are of lengths p, q, r, respectively. Let k = p + q + r - 1 . In this paper, we obtain the exact value of e x (n , θ (p , q , r)) and characterize the unique extremal graph for n ≥ 9 k 2 - 3 k and any p, q, r with different parities. This extends a known result on odd cycles. [ABSTRACT FROM AUTHOR]

Colourful connection concepts in graph theory such as rainbow connection, proper connection, odd connection or conflict-free connection have received a lot of attention. For an integer k ≥ 1 we call a path P in a graph Gk-colourful, if at least k vertices of P are pairwise differently coloured. A graph G is k-colourful connected, if any two vertices of G are connected by a k-colouful path. Now we call the least integer k, which makes Gk-colourful connected, the k-colourful connection number of G. In this paper, we introduce the (strong, internal) k-colourful connection number of a graph, establish bounds for our new invariants in several graph classes as well as compute exact values for k ∈ [ 3 ] . [ABSTRACT FROM AUTHOR]

For an even graph G and non-negative integers r and s, the pair (r , s) is an admissible pair if 4 r + 8 s = | E (G) |. If G admits a decomposition into r copies of C 4 , the cycle of length four, and s copies of C 8 , the cycle of length eight, for every admissible pair (r , s) , then G has a { C 4 r , C 8 s } -decomposition. In this paper, a necessary and sufficient condition is obtained for the existence of a { C 4 r , C 8 s } -decomposition of the complete k-partite graph K a 1 , a 2 , ⋯ , a k , where k ≥ 3. Further, a characterization is obtained for the graph K m × K n , where × denotes the tensor product of graphs, to admit a { C 4 r , C 8 s } -decomposition. [ABSTRACT FROM AUTHOR]