Search

In 2012, Henning and Yeo have posed the conjecture that a bipartite 3-regular digraph contains two disjoint cycles of different lengths, and Tan has proved that a 3-regular bipartite digraph, which possesses a cycle factor with at least two cycles, does indeed have two disjoint cycles of different lengths. In this paper, we prove that every 3-regular digraph, which possesses a cycle factor with at least three cycles, contains two disjoint cycles of different lengths, except for the digraph that is isomorphic to the D 2 n 2 ( n ≥ 3 ). [ABSTRACT FROM AUTHOR]

The cochromatic number Z(G) of a graph G is the fewest number of colors needed to color the vertices of G so that each color class is a clique or an independent set. In a fractional cocoloring of G a non-negative weight is assigned to each clique and independent set so that for each vertex v, the sum of the weights of all cliques and independent sets containing v is at least one. The smallest total weight of such a fractional cocoloring of G is the fractional cochromatic number Z f (G) . In this paper we prove results for the fractional cochromatic number Z f (G) that parallel results for Z(G) and the well studied fractional chromatic number χ f (G) . For example Z f (G) = χ f (G) when G is triangle-free, except when the only nontrivial component of G is a star. More generally, if G contains no k-clique, then Z f (G) ≤ χ f (G) ≤ Z f (G) + R (k , k) , where R(k, k) is the minimum integer n such that every n-vertex graph has a k-clique or an independent set of size k. Moreover, every graph G with χ f (G) = m contains a subgraph H with Z f (H) ≥ (1 4 - o (1)) m log 2 m . We also prove that the maximum value of Z f (G) over all graphs G of order n is Θ (n / log n) , and the maximum over all graphs embedded on an orientable surface of genus g is Θ (g / log g) . [ABSTRACT FROM AUTHOR]

In this paper, we study the flexibility of two planar graph classes H 1 , H 2 , where H 1 , H 2 denote the set of all hopper-free planar graphs and house-free planar graphs, respectively. Let G be a planar graph with a list assignment L. Suppose a preferred color is given for some of the vertices. We prove that if G ∈ H 1 or G ∈ H 2 such that all lists have size at least 5, then there exists an L-coloring respecting at least a constant fraction of the preferences. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with order n and adjacency matrix A (G) . The characteristic polynomial of G is defined by ϕ (G ; λ) = det (λ I - A (G)) = ∑ i = 0 n a i (G) λ n - i , where a i (G) is called the i-th adjacency coefficient of G. Denote by B n , m the collection of all connected bipartite graphs having n vertices and m edges. A bipartite graph G is referred as 4-Sachs optimal if a 4 (G) = min { a 4 (H) ∣ H ∈ B n , m }. For any given integer pair (n, m), in this paper we investigate the 4-Sachs optimal bipartite graphs. Firstly, we show that each 4-Sachs optimal bipartite graph is a difference graph. Then we deduce some structural properties on 4-Sachs optimal bipartite graphs. Especially, we determine the unique 4-Sachs optimal bipartite (n, m)-graphs for n ≥ 5 and n - 1 ≤ m ≤ 2 (n - 2) . Finally, we provide a method to construct a class of cospectral difference graphs, which disprove a conjecture posed by Andelić et al. (J Czech Math 70:1125–1138, 2020). [ABSTRACT FROM AUTHOR]

In this paper, we give a series of counterexamples to negate a conjecture and answer an open question on the k-power domination of regular graphs [see Dorbec et al. (SIAM J Discrete Math 27:1559–1574, 2013)]. Furthermore, we focus on the study of k-power domination of claw-free graphs. We show that for l ∈ { 2 , 3 } and k ≥ l , the k-power domination number of a connected claw-free (k + l + 1) -regular graph on n vertices is at most n k + l + 2 , and this bound is tight. [ABSTRACT FROM AUTHOR]

Let G be a graph, a dominating induced matching (DIM) of G is an induced matching that dominates every edge of G. In this paper we show that if a graph G has a DIM, then χ (G) ≤ 3 . Also, it is shown that if G is a connected graph whose all edges can be partitioned into DIM, then G is either a regular graph or a biregular graph and indeed we characterize all graphs whose edge set can be partitioned into DIM. Also, we prove that if G is an r-regular graph of order n whose edges can be partitioned into DIM, then n is divisible by 2 r - 1 r - 1 and n = 2 r - 1 r - 1 if and only if G is the Kneser graph with parameters r - 1 , 2 r - 1 . [ABSTRACT FROM AUTHOR]

Let G be a graph with an edge-coloring c, and let δ c (G) denote the minimum color-degree of G. A subgraph of G is called rainbow if any two edges of the subgraph have distinct colors. In this paper, we consider color-degree conditions for the existence of rainbow triangles in edge-colored graphs. At first, we give a new proof for characterizing all extremal graphs G with δ c (G) ≥ n 2 that do not contain rainbow triangles, a known result due to Li et al. Then, we characterize all complete graphs G without rainbow triangles under the condition δ c (G) = l o g 2 n , extending a result due to Li, Fujita and Zhang. Hu, Li and Yang showed that G contains two vertex-disjoint rainbow triangles if δ c (G) ≥ n + 2 2 when n ≥ 20 . We slightly refine their result by showing that the result also holds for n ≥ 6 , filling the gap of n from 6 to 20. Finally, we prove that if δ c (G) ≥ n + k 2 then every vertex of an edge-colored complete graph G is contained in at least k rainbow triangles, generalizing a result due to Fujita and Magnant. At the end, we mention some open problems. [ABSTRACT FROM AUTHOR]

A strong edge-coloring of a graph G is a proper edge coloring such that every path of length 3 uses three different colors. The strong chromatic index of G, denoted by χ s ′ (G) , is the least possible number of colors in a strong edge-coloring of G. In this paper, we prove that if G is a claw-free subcubic graph other than the prism graph, then χ s ′ (G) ≤ 8 . [ABSTRACT FROM AUTHOR]

A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number is the minimum cardinality of a paired-dominating set of G. The paired-domination subdivision number is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the paired-domination number. It was conjectured that the paired-domination subdivision number is at most n - 1 for every connected graph G of order n ≥ 3 which does not contain isolated vertices. In this paper, we settle the conjecture in the affirmative. [ABSTRACT FROM AUTHOR]

Berge Conjecture states that every bridgeless cubic graph has 5 perfect matchings such that each edge is contained in at least one of them. In this paper, we show that Berge Conjecture holds for bridgeless cubic graphs which have two perfect matchings with at most one common edge. [ABSTRACT FROM AUTHOR]

Let H be a graph possibly with loops and G a multigraph without loops. G is said to be H-colored if there exists a function c: E(G) → V(H). A cycle ( v 0 , e 0 , v 1 , e 1 , ... , e k - 1 , v k = v 0 ) in G, where e i = v i v i + 1 for every i in {0, ... , k - 1 }, is an H-cycle if and only if (c( e 0 ), a 0 , c( e 1 ), ... , c( e k - 2 ), a k - 2 , c( e k - 1 ), a k - 1 , c( e 0 )) is a walk in H, with a i = c( e i )c( e i + 1 ) for every i in {0, ... , k - 1 } (indices modulo k). If H is a complete graph without loops, an H-walk is called properly colored walk. The problem of check whether an edge-colored graph G contains a properly colored cycle was studied first by Grossman and Häggkvist. Subsequently Yeo gave a sufficient condition which guarantee the existence of a properly colored cycle. In this paper we will extend Yeo's result for the case where stronger requirements are enforced for a properly colored cycle to be eligible, based on the adjacencies of a graph whose vertices are in bijection with the colors. The main result establishes that if H is a graph without loops and G is an H-colored multigraph such that (1) H and G have no isolated vertices, (2) G has no H-cycles and (3) for every x in V(G), G x is a complete k x -partite graph for some k x in N . Then there exists a vertex z in V(G) such that every connected component D of G - z satisfies that {e ∈ E(G) : e = z u for some u in V(D)} is an independent set in G z (where for w in V(G), G w is an associated graph to the vertex w, respect to the H-coloring of G). [ABSTRACT FROM AUTHOR]

The classical extremal problem is that of computing the maximum number of edges in an F-free graph. In particular, Turán's theorem entirely resolves the case where F = K r + 1 . Later results, known as supersaturation theorems, proved that in a graph containing more edges than the extremal number, there must also be many copies of K r + 1 . Alon and Shikhelman introduced a broader class of extremal problems, asking for the maximum number of copies of a graph T in an F-free graph (so that T = K 2 is the classical extremal number). In this paper we determine some of these generalized extremal numbers when T and F are stars or cliques and prove some supersaturation results for them. [ABSTRACT FROM AUTHOR]

Origami, where two-dimensional sheets are folded into complex structures, is rich with combinatorial and geometric structure, most of which remains to be fully understood. In this paper we consider flat origami, where the sheet of material is folded into a two-dimensional object, and consider the mountain (convex) and valley (concave) creases that result, called a MV assignment of the crease pattern. An open problem is to count the number locally valid MV assignments μ of a given flat-foldable crease pattern C, where locally valid means that each vertex will fold flat under μ with no self-intersections of the folded material. In this paper we solve this problem for a large family of crease patterns by creating a planar graph C ∗ whose 3-colorings are in one-to-one correspondence with the locally valid MV assignments of C. This reduces the problem of enumerating locally valid MV assignments to the enumeration of 3-colorings of graphs. [ABSTRACT FROM AUTHOR]

Given two graphs G and H, the k-colored Gallai–Ramsey number g r k (G : H) is defined to be the minimum integer n such that every k-coloring of the complete graph on n vertices contains either a rainbow copy of G or a monochromatic copy of H. In this paper, we consider g r k (K 3 : H) , where H is a connected graph with five vertices and at most six edges. There are in total thirteen graphs in this graph class, and the Gallai–Ramsey numbers for eight of them have been studied step by step in several papers. We determine all the Gallai–Ramsey numbers for the remaining five graphs, and we also obtain some related results for a class of unicyclic graphs. As applications, we find the mixed Ramsey spectra S (n ; H , K 3) for these graphs by using the Gallai–Ramsey numbers. [ABSTRACT FROM AUTHOR]

A strong edge coloring of a graph G is a proper edge coloring of G such that every color class is an induced matching. The minimum number of colors required is termed the strong chromatic index. In this paper we determine the exact value of the strong chromatic index of all unitary Cayley graphs. Our investigations reveal an underlying product structure from which the unitary Cayley graphs emerge. We then go on to give tight bounds for the strong chromatic index of the Cartesian product of two trees, including an exact formula for the product in the case of stars. Further, we give bounds for the strong chromatic index of the product of a tree with a cycle. For any tree, those bounds may differ from the actual value only by not more than a small additive constant (at most 2 for even cycles and at most 4 for odd cycles), moreover they yield the exact value when the length of the cycle is divisible by 4. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph, and D(G) be the distance matrix of G. Suppose that D max (G) and λ 1 (G) are the maximum row sum and the spectral radius of D(G), respectively. In this paper, we give a lower bound for D max (G) - λ 1 (G) , and characterize the extremal graphs attaining the bound. As a corollary, we solve a conjecture posed by Liu, Shu and Xue. [ABSTRACT FROM AUTHOR]

A pebble assignment (S G) on a finite simple graph G is a distribution of a finite number of pebbles on the vertices of G. A standard pebbling move consists of removing two pebbles from a vertex x of G while adding one pebble to a vertex adjacent to x. In this paper, we introduce the new notion of a pebble assignment graph. Formally, this is a Hasse diagram [ S G ] whose nodes correspond to all assignments that can be reached from (S G) by applying a sequence of pebbling moves. Edges of [ S G ] adjoin any two assignments where one can be reached from the other via a single pebbling move (i.e., from "parent" to "child"). We investigate properties of this new class of graphs, addressing such questions as which abstract graphs can be realized as pebbling assignment graphs, and for which graphs G does there exist an assignment (S G) such that [ S G ] ≅ G ? [ABSTRACT FROM AUTHOR]

Henning et al. (Discrete Appl Math 162:399–403, 2014) proved that if G is a bipartite, cubic graph of order n and of girth at least 6, then i (G) ≤ 4 11 n . In this paper, we improve the 4 11 -bound to a 5 14 -bound, and prove that if G is a bipartite, cubic graph of order n and of girth at least 6, then i (G) ≤ 5 14 n . [ABSTRACT FROM AUTHOR]

A weakly distance-regular digraph is thick if its attached scheme is regular. In this paper, we show that each commutative thick weakly distance-regular digraph has a thick weakly distance-regular subdigraph such that the corresponding quotient digraph falls into six families of thick weakly distance-regular digraphs up to isomorphism. [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]

Given a connected graph G = (V (G) , E (G)) , the length of a shortest path from a vertex u to a vertex v is denoted by d(u, v). For a proper subset W of V(G), let m(W) be the maximum value of d(u, v) as u ranging over W and v ranging over V (G) \ W . The proper subset W = { w 1 , ... , w | W | } is a completeness-resolving set of G if Ψ W : V (G) \ W ⟶ [ m (W) ] | W | , u ⟼ (d (w 1 , u) , ... , d (w | W | , u)) is a bijection, where [ m (W) ] | W | = { (a (1) , ... , a (| W |)) ∣ 1 ≤ a (i) ≤ m (W) for each i = 1 , ... , | W | }. A graph is completeness-resolvable if it admits a completeness-resolving set. In this paper, we first construct the set of all completeness-resolvable graphs by using the edge coverings of some vertices in given bipartite graphs, and then establish posets on some subsets of this set by the spanning subgraph relationship. Based on each poset, we find the maximum graph and give the lower and upper bounds for the number of edges in a minimal graph. Furthermore, minimal graphs satisfying the lower or upper bound are characterized. [ABSTRACT FROM AUTHOR]

This paper concentrates on the set V n of weighted Dyck paths of length 2n with special restrictions on the level of valleys. We first give its explicit formula of the counting generating function in terms of certain weight functions. When the weight functions are specialized, some connections are builded between V n and other classical combinatorial structures such as (a, b)-Motzkin paths, q-Schröder paths, Delannoy paths and complete k-ary trees. Some bijections are also established between these settings and V n subject to certain special weight functions. [ABSTRACT FROM AUTHOR]

Motivated by conjectures of Karloff, and Van Dam and Sotirov on the smallest eigenvalues of Johnson and Hamming graphs, Brouwer, Cioabă, Ihringer and McGinnis obtained some new results involving the eigenvalues of various graphs coming from association schemes and posed some conjectures related to the eigenvalues of Grassmann graphs, Bilinear forms graphs and Hermitian forms graphs. In this paper, we prove some of their conjectures. [ABSTRACT FROM AUTHOR]

A k-hypertournament H consists of a pair (V(H), A(H)), where V(H) is a non-empty finite set of vertices and A(H) contains exactly one permutation of S as an arc for every k-size subset S of V. A k-hypertournament H = (V (H) , A (H)) on n vertices is ∑ -regular if d e g + (v) = d e g - (v) = n - 1 2 n - 2 k - 2 for all v ∈ V (H) . M. Surmacs introduced the ∑ -regularity in hypertournament and prove that every ∑ -regular k-hypertournament H (where 2 ≤ k ≤ n - 2 ) on n vertices is arc-pancyclic, i.e., every arc of H is on an ℓ -cycle for all 3 ≤ ℓ ≤ n . In this paper, we prove that every ∑ -regular k-hypertournament H (where 3 ≤ k ≤ n - 2 ) on n vertices is arc-antipancyclic, i.e., every arc of H has an ℓ -bypass for all 3 ≤ ℓ ≤ n - 1 , which is an extension of Alspach's result. [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]

A double Roman dominating function (DRDF) on a graph G = (V , E) is a function f : V → { 0 , 1 , 2 , 3 } having the property that if f (v) = 0 , then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f (w) = 3 , and if f (v) = 1 , then vertex v must have at least one neighbor w with f (w) ≥ 2 . The weight of a DRDF is the sum of its function values over all vertices, and the double Roman domination number γ dR (G) is the minimum weight of a DRDF on G. Recently, Khoeilar et al. (Discrete Appl Math 270:159–167, 2019) proved that a connected graph G of order n with minimum degree two different from C 5 and C 7 , satisfies γ dR (G) ≤ 11 10 n. In this paper, we show that this upper bound can be improved to 20 19 n if G is restricted to connected graphs of order n with minimum degree at least two and no C 5 -cycle such that G ∉ { C 7 , C 11 , C 13 , C 17 }. Moreover, we provide an infinite family of graphs attaining this bound. [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]

Let F be a family of graphs. A graph G is called F -free if for any F ∈ F , there is no subgraph of G isomorphic to F. Given a graph T and a family of graphs F , the generalized Turán number of F is the maximum number of copies of T in an F -free graph on n vertices, denoted by e x (n , T , F) . A linear forest is a graph whose connected components are all paths or isolated vertices. Let L n , k be the family of all linear forests of order n with k edges and K s , t ∗ be a graph obtained from K s , t by substituting the part of size s with a clique of order s. In this paper, we determine the exact values of e x (n , K s , L n , k) and e x (n , K s , t ∗ , L n , k) . Also, we study the case of this problem when the "host graph" is bipartite. Denote by e x bip (n , T , F) the maximum possible number of copies of T in an F -free bipartite graph with each part of size n. We determine the exact value of e x bip (n , K s , t , L n , k) . Our proof is mainly based on the shifting method. [ABSTRACT FROM AUTHOR]

In 1988, Beck (J Algebra 116:208–226, 1988) conjectured that the chromatic number and clique number is the same for the graphs associated to any commutative ring with unity. In 1993, Anderson and Naseer (J Algebra 159:500–514, 1993) disproved the conjecture with a counterexample. In this paper, we find the clique number and bounds for the chromatic number of the graph associated with the finite product of commutative rings with unity. Also we show that some of the results, proved in (Anderson and Naseer in J Algebra 159:500–514, 1993, Beck in J Algebra 116:208–226, 1988) are consequences of our results. In addition, we have constructed a new family of counterexamples of the above conjecture. [ABSTRACT FROM AUTHOR]

For S ⊆ V (G) , we define S ¯ = V (G) \ S . A set S ⊆ V (G) is called a super dominating set if for every vertex u ∈ S ¯ , there exists v ∈ S such that N (v) ∩ S ¯ = { u } . The super domination number γ sp (G) of G is the minimum cardinality among all super dominating sets in G. The super domination subdivision number s d γ sp (G) of a graph G is the minimum number of edges that must be subdivided in order to increase the super domination number of G. In this paper, we investigate the ratios between super domination and other domination parameters in trees. In addition, we show that for any nontrivial tree T, 1 ≤ s d γ sp (T) ≤ 2 , and give constructive characterizations of trees whose super domination subdivision number are 1 and 2, respectively. [ABSTRACT FROM AUTHOR]

For given 3-uniform hypergraphs H and G , the Ramsey number R (H , G) is the smallest number N such that each red-blue coloring of the edges of the complete 3-uniform hypergraph K N 3 contains either a red copy of H or a blue copy of G . Let C n 3 , P n 3 and S n 3 denote the 3-uniform loose cycle, loose path and star with n edges, respectively. The 2-color Ramsey number of 3-uniform loose path and loose cycle has been determined completely by several researchers. In this paper, we prove that R (P m 3 , S n 3) = 2 n + 1 + m - 1 2 for all m, n with n ≥ 2 m ≥ 2 and R (P m 3 , S n 3) = 2 m + 1 for all m, n with m ≥ 9 4 n . [ABSTRACT FROM AUTHOR]

Quasi-strongly regular digraphs are a combinatorial generalization of strongly regular digraphs and quasi-strongly regular graphs. A quasi-strongly regular digraph Γ with parameters (n , k , t , a ; c 1 , c 2 , ... , c p) is a k-regular digraph on n vertices such that each vertex is incident with t undirected edges, for any two distinct vertices x, y the number of paths of length 2 from x to y is a if x → y and c i otherwise, and for each c i there exist two distinct vertices x ↛ y such that the number of paths of length 2 from x to y is c i , where i ∈ { 1 , 2 , ... , p } . We call p the grade of Γ . In this paper, we first study quasi-strongly regular digraphs of grade 2 and obtain some constraints between the parameters. Moreover, we present some constructions of quasi-strongly regular digraphs from different combinatorial objects. Finally, we introduce a variation of quasi-strongly regular digraphs and provide some constructions. [ABSTRACT FROM AUTHOR]

Divisible design graphs were introduced in 2011 by Haemers, Kharaghani and Meulenberg. Further, divisible design graphs which can be obtained as Cayley graphs were recently studied by Kabanov and Shalaginov. In this paper we give new constructions of divisible design Cayley graphs and classify divisible design Cayley graphs on v ≤ 27 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]

Let G be a simple undirected graph. For any real number α ∈ [ 0 , 1 ] , Nikiforov defined the A α -matrix of G as A α (G) = α D (G) + (1 - α) A (G) , where A(G) and D(G) are the adjacency matrix and the degree diagonal matrix of G respectively. The largest eigenvalue of A α (G) is called the A α -spectral radius of G. In this paper, we give sharp upper bounds on the A α -spectral radius of C 4 -free graphs and Halin graphs for α ∈ [ 1 / 2 , 1) respectively. [ABSTRACT FROM AUTHOR]

It is well-known that every triangulation on a closed surface F 2 has a spanning quadrangulation Q, and in particular, Q is bipartite if F 2 is the sphere. In other words, every triangulation on the sphere has a polychromatic 2-coloring, which is a (not necessarily proper) 2-coloring of a graph on a closed surface without a monochromatic face. In this paper, we consider the balancedness of a polychromatic 2-coloring of graphs, that is, whether the difference in size of each color class is at most one. We verify that every 3-colorable triangulation has a balanced polychromatic 2-coloring. On the other hand, we construct an infinite family of triangulations G with order n on the sphere such that for every polychromatic 2-coloring of G, the size of color classes differs at least n 3 - 2 . Then we conjecture that every triangulation on the sphere has a polychromatic 2-coloring whose size of color classes differs at most one-third of the number of vertices, and we give partial solutions for the conjecture. [ABSTRACT FROM AUTHOR]

Fix a hypergraph F . A hypergraph H is called a Berge copy of F or Berge- F if we can choose a subset of each hyperedge of H to obtain a copy of F . A hypergraph H is Berge- F -free if it does not contain a subhypergraph which is Berge copy of F . This is a generalization of the usual, graph-based Berge hypergraphs, where F is a graph. In this paper, we study extremal properties of hypergraph based Berge hypergraphs and generalize several results from the graph-based setting. In particular, we show that for any r-uniform hypergraph F , the sum of the sizes of the hyperedges of a (not necessarily uniform) Berge- F -free hypergraph H on n vertices is o (n r) when all the hyperedges of H are large enough. We also give a connection between hypergraph based Berge hypergraphs and generalized hypergraph Turán problems. [ABSTRACT FROM AUTHOR]

DP-coloring (also known as correspondence coloring) as a generalization of list coloring was introduced recently by Dvořák and Postle. In this paper, we prove that planar graphs without cycles of length from 4 to 7 and intersecting triangles are DP-3-colorable and therefore 3-choosable. We use identification of vertices in the proof, and actually prove stronger statements that every pre-coloring of some short cycles can be extended to the whole graph. [ABSTRACT FROM AUTHOR]

Let μ (G) denote the mean color number of a graph G. Dong proposed two mean color conjectures. One is that for any graph G and a vertex w in G with d (w) ≥ 1 , if H is a graph obtained from G by deleting all but one of the edges which are incident to w, then μ (G) ≥ μ (H) . The other is that for any graph G and a vertex w in G, μ (G) ≥ μ ((G - w) ∪ K 1) . In this paper, we show that the two conjectures hold under the condition that w is a simplicial vertex in G. And when G is a connected (n, m)-graph and w is not a cut vertex in G with d (w) = n - 1 , if m ≤ (2 2 + 2) n - 4.5 - 2 , the second conjecture holds too. The two conjectures also hold for some special cases, such as wheels and chordal graphs (Dong in J Combin Theory Ser B 87: 348–365, 2003). [ABSTRACT FROM AUTHOR]

A noncrossing forest is a forest drawn on n points numbered in counterclockwise order on a circle in such a way that its edges are rectilinear and do not cross. Utilizing analytic combinatorics, Flajolet and Noy obtained the number of noncrossing forests with n vertices and k components. In this paper, we will give a new representation for noncrossing forests. Based on such respresentation, we establish a decomposition algorithm and a merging algorithm, which leads to a bijection between labeled noncrossing forests and sets of rooted matches. As an application, we derive a new formula, which is a refinement of the formula given by Flajolet and Noy. [ABSTRACT FROM AUTHOR]

Let D be a strong balanced bipartite digraph on 2a vertices. For x , y , z ∈ V (D) , if x → z and y → z , then we call the pair { x , y } dominating; if z → x and z → y , then we call the pair { x , y } dominated. In 2017, Adamus [Graphs and Combinatorics, 33(2017) 43–51] proved that if d (x) + d (y) ≥ 3 a whenever { x , y } is a dominating or dominated pair, then D is Hamiltonian. In 2021, Adamus [Discrete Mathematics, 344(3) (2021) 112240] proved that if only every dominating pair of vertices { x , y } in D satisfies d (x) + d (y) ≥ 3 a + 1 , then D is Hamiltonian. In this paper, we show that the same conclusion is reached if we replace 3 a + 1 with 3a in the above condition. The lower bound for 3a is sharp. [ABSTRACT FROM AUTHOR]

Zero forcing (zero forcing number, denoted by F(G)) of a connected graph G, which proposed by the AIM-minimum rank group in 2008, has been received much attention. In 2015, Davila introduced total forcing which is as a strengthening form of zero forcing. The total forcing number of G is the minimum cardinality of a total forcing set in G, denoted by F t (G) . It is easy to deduce that for any graph G, F (G) ≤ F t (G) ≤ 2 F (G) . In addition, we know that F t (T) ≥ F (T) + 1 for a tree T. Our interest is to study the structure of the tree T with F t (T) = 2 F (T) . In the paper, we characterize all trees meets the condition. In fact, these trees can be reconstructed by beginning with a path through repeating a tree operation. [ABSTRACT FROM AUTHOR]

A degree sequence is a list of non-negative integers, D = d 1 , d 2 , ... , d n . It is called graphical if there exists a simple graph G such that the degree of the ith vertex is d i ; G is then said to be a realization of D. A tree degree sequence is one that is realized by a tree. In this paper we consider the problem of packing tree degree sequences: given k tree degree sequences, do they have simultaneous (i.e. on the same vertices) edge-disjoint realizations? We conjecture that this is true for any arbitrary number of tree degree sequences whenever they share no common leaves (degree-1 vertices). This conjecture is inspired by work of Kundu (SIAM J Appl Math 28:290–302, 1975) that showed it to be true for 2 and 3 tree degree sequences. In this paper, we give a proof for 4 tree degree sequences and a computer-aided proof for 5 tree degree sequences. We also make progress towards proving our conjecture for arbitrary k. We prove that k tree degree sequences without common leaves and at least 2 k - 4 vertices which are not leaves in any of the trees always have edge-disjoint tree realizations. Additionally, we show that to prove the conjecture, it suffices to prove it for n ≤ 4 k - 2 vertices. The main ingredient in all of the presented proofs is to find rainbow matchings in certain configurations. [ABSTRACT FROM AUTHOR]

A pebbling move on a graph removes two pebbles from a vertex and adds one pebble to an adjacent vertex. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using pebbling moves. The optimal pebbling number π opt is the smallest number m needed to guarantee a pebble distribution of m pebbles from which any vertex is reachable. The optimal pebbling number of the square grid graph P n □ P m was investigated in several papers (Bunde et al. in J Graph Theory 57(3):215–238, 2008; Xue and Yerger in Graphs Combin 32(3):1229–1247, 2016; Győri et al. in Period Polytech Electr Eng Comput Sci 61(2):217–223 2017). In this paper, we present a new method using some recent ideas to give a lower bound on π opt . We apply this technique to prove that π opt (P n □ P m) ≥ 2 13 n m . Our method also gives a new proof for π opt (P n) = π opt (C n) = 2 n 3 . [ABSTRACT FROM AUTHOR]

A connected graph G has property E(m, n) (or more briefly "G is E(m, n)") if for every pair of disjoint matchings M and N in G with | M | = m and | N | = n respectively, there is a perfect matching F in G such that M ⊆ F and N ∩ F = ∅ . In particular, a graph which has the E(m, 0) property is said to be m-extendable. Also a graph G which has the property that G - u - v has a perfect matching for every pair of distinct vertices u and v is said to be bicritical. In the present paper we investigate further the interrelation between extendability and criticality. In Lovász and Plummer (Matching theory, North-Holland Publisher, Amsterdam, 1986) author proved that a 2-extendable graph is either 1-extendable and bipartite, or else bicritical (clearly a graph cannot be both). In the present paper we generalize this result by extending the notion of bicriticality in several ways and studying the relationships of these extensions to extendability. [ABSTRACT FROM AUTHOR]

This paper extends the concept of filter on X into (X, f), where X is a finite underlying set and f is a symmetric submodular function from 2 X to N. Then, we show a cryptomorphism between a free ultrafilter and co-tangle on (X, f). The paper also provides game-theoretical interpretations of a branch decomposition tree and a free ultrafilter on (X, f). [ABSTRACT FROM AUTHOR]

We study the problem of deciding whether a crease pattern can be folded by simple folds (folding along one line at a time) under the infinite all-layers model introduced by Akitaya et al. (J Inform Process 25:582–589, 2017), in which each simple fold is defined by an infinite line and must fold all layers of paper that intersect this line. This model is motivated by folding in manufacturing such as sheet-metal bending. We improve on Arkin et al. (Comput Geom Theory Appl 29(1):23–46, 2014) by giving a deterministic O(n)-time algorithm to decide simple foldability of 1D crease patterns in the all-layers model. Then we extend this 1D result to 2D, showing that simple foldability in the infinite all-layers model can be decided in linear time for both unassigned and assigned axis-aligned orthogonal crease patterns on axis-aligned 2D orthogonal paper. On the other hand, we show that simple foldability is strongly NP-complete if a subset of the creases have a mountain–valley assignment, even for axis-aligned rectangular paper. [ABSTRACT FROM AUTHOR]

We study the list chromatic number of the Cartesian product of any graph G and a complete bipartite graph with partite sets of size a and b, denoted χ ℓ (G □ K a , b) . We have two motivations. A classic result on the gap between list chromatic number and the chromatic number tells us χ ℓ (K a , b) = 1 + a if and only if b ≥ a a . Since χ ℓ (K a , b) ≤ 1 + a for any b ∈ N , this result tells us the values of b for which χ ℓ (K a , b) is as large as possible and far from χ (K a , b) = 2 . In this paper we seek to understand when χ ℓ (G □ K a , b) is far from χ (G □ K a , b) = max { χ (G) , 2 } . It is easy to show χ ℓ (G □ K a , b) ≤ χ ℓ (G) + a . Borowiecki et al. (Discrete Math 306:1955–1958, 2006) showed that this bound is attainable if b is sufficiently large; specifically, χ ℓ (G □ K a , b) = χ ℓ (G) + a whenever b ≥ (χ ℓ (G) + a - 1) a | V (G) | . Given any graph G and a ∈ N , we wish to determine the smallest b such that χ ℓ (G □ K a , b) = χ ℓ (G) + a . In this paper we show that the list color function, a list analogue of the chromatic polynomial, provides the right concept and tool for making progress on this problem. Using the list color function, we prove a general improvement on Borowiecki et al.'s (2006) result, and we compute the smallest such b for some large families of chromatic-choosable graphs. [ABSTRACT FROM AUTHOR]