Search

It is currently an unsolved problem to determine whether, for every 2-list assignment L of a ▵ -free planar graph G, there exists an independent set A L such that G [ V G \ A L ] is L-colorable. However, in this paper, we take a slightly different approach to the above problem. We prove the N P -completeness of the decision problem of determining an independent set A such that G [ V G \ A ] is 2-choosable for ▵ -free, 4-colorable graphs of diameter 3. Building upon this notion, we examine the computational complexity of two optimization problems: minimum near-3-choosability and minimum 2-choosable-edge-deletion. In the former problem, the goal is to find an independent set A of minimum size in a given graph G, such that the induced subgraph G [ V G \ A ] is 2-choosable. We establish that this problem is N P -hard to approximate within a factor of | V G | 1 - ϵ for any ϵ > 0 , for planar bipartite graphs of arbitrary large girth. On the other hand, the problem of minimum 2-choosable-edge-deletion involves determining an edge set F ⊆ E G of minimum cardinality such that the spanning subgraph G [ E G \ F ] is 2-choosable. We prove that this problem can be approximated within a factor of O (log | V G |) . [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph with no isolated vertices. A vertex v totally dominates a vertex w ( w ≠ v ), if v is adjacent to w. A set D ⊆ V called a total dominating set of G if every vertex v ∈ V is totally dominated by some vertex in D. The minimum cardinality of a total dominating set is the total domination number of G and is denoted by γ t (G) . A total dominator coloring of graph G is a proper coloring of vertices of G, so that each vertex totally dominates some color class. The total dominator chromatic number χ td (G) of G is the least number of colors required for a total dominator coloring of G. The Total Dominator Coloring problem is to find a total dominator coloring of G using the minimum number of colors. It is known that the decision version of this problem is NP-complete for general graphs. We show that it remains NP-complete even when restricted to bipartite, planar and split graphs. We further study the Total Dominator Coloring problem for various graph classes, including trees, cographs and chain graphs. First, we characterize the trees having χ td (T) = γ t (T) + 1 , which completes the characterization of trees achieving all possible values of χ td (T) . Also, we show that for a cograph G, χ td (G) can be computed in linear-time. Moreover, we show that 2 ≤ χ td (G) ≤ 4 for a chain graph G and then we characterize the class of chain graphs for every possible value of χ td (G) in linear-time. [ABSTRACT FROM AUTHOR]

Let G be a graph, and let Q(G) and L(G) denote the signless Laplacian matrix and the Laplacian matrix of G, respectively. The polynomials ϕ (Q (G) , x) = per (x I n - Q (G)) and ϕ (L (G) , x) = per (x I n - L (G)) are called signless Laplacian permanental polynomial and Laplacian permanental polynomial of G, respectively. In this paper, we investigate the properties of roots of ϕ (Q (G) , x) . We obtain the real root distribution of ϕ (Q (G) , x) . In particular, using the Gallai–Edmonds structure theorem, we determine the structures of graphs G whose roots of signless Laplacian permanental polynomial of G contain no positive integer p, where p is the minimum vertex degree of G. And we determine completely the graphs each of which having the multiplicity of the integer root p is equal to the deficiency of a maximum p-pendant structure of the graph. These results extend the conclusion obtained by Faria (Linear Algebra Appl 299:15–35, 1995). Furthermore, we give an algorithm to calculate the multiplicity of the root p of ϕ (Q (G) , x) . And we also determine the relation between the multiplicity of the root p of ϕ (Q (G) , x) and the matching number of G. Finally, we investigate the properties of roots of Laplacian permanental polynomial of non-bipartite graphs. And some open problems are presented. [ABSTRACT FROM AUTHOR]

In this paper, we apply the Turán sieve and the simple sieve developed by R. Murty and the first author to study problems in random graph theory. In particular, we obtain upper and lower bounds on the probability of a graph on n vertices having diameter 2 (or diameter 3 in the case of bipartite graphs) with edge probability p where the edges are chosen independently. An interesting feature revealed in these results is that the Turán sieve and the simple sieve "almost completely" complement each other. As a corollary to our result, we note that the probability of a random graph having diameter 2 approaches 1 as n → ∞ for constant edge probability p = 1 / 2 . [ABSTRACT FROM AUTHOR]

For an n-vertex graph G, a fractional matching of G is a function f giving each edge a real number in [0, 1] such that ∑ e ∈ Γ (v) f (e) ≤ 1 for each vertex v ∈ V (G) , where Γ (v) is the set of edges incident to v. A fractional perfect matching is a fractional matching f with ∑ e ∈ E (G) f (e) = n 2 . In this paper, we establish tight lower bounds on the size and the spectral radius of G to guarantee that G has a fractional perfect matching, respectively. In addition, we investigate the relationship between fractional perfect matching and P ⩾ 2 -factor, and give some sufficient conditions for a graph to have a P ⩾ 2 -factor. [ABSTRACT FROM AUTHOR]

An independent set of a graph G is a vertex subset I such that there is no edge joining any two vertices in I. Imagine that a token is placed on each vertex of an independent set of G. The TS - ( TS k -) reconfiguration graph of G takes all non-empty independent sets (of size k) as its nodes, where k is some given positive integer. Two nodes are adjacent if one can be obtained from the other by sliding a token on some vertex to one of its unoccupied neighbors. This paper focuses on the structure and realizability of these reconfiguration graphs. More precisely, we study two main questions for a given graph G: (1) Whether the TS k -reconfiguration graph of G belongs to some graph class G (including complete graphs, paths, cycles, complete bipartite graphs, connected split graphs, maximal outerplanar graphs, and complete graphs minus one edge) and (2) If G satisfies some property P (including s-partitedness, planarity, Eulerianity, girth, and the clique's size), whether the corresponding TS - ( TS k -) reconfiguration graph of G also satisfies P , and vice versa. Additionally, we give a decomposition result for splitting a TS k -reconfiguration graph into smaller pieces. [ABSTRACT FROM AUTHOR]

A graph H = (W , E H) is said to have bandwidth at most b if there exists a labeling of W as w 1 , w 2 , ⋯ , w n such that | i - j | ≤ b for every edge w i w j ∈ E H . We say that H is a balanced (β , Δ) -graph if it is a bipartite graph with bandwidth at most β | W | and maximum degree at most Δ , and it also has a proper 2-coloring χ : W → [ 2 ] such that | | χ - 1 (1) | - | χ - 1 (2) | | ≤ β | χ - 1 (2) | . In this paper, we prove that for every γ > 0 and every natural number Δ , there exists a constant β > 0 such that for every balanced (β , Δ) -graph H on n vertices we have R (H , H , C n) ≤ (3 + γ) n for all sufficiently large odd n. The upper bound is sharp for several classes of graphs. Let θ n , t be the graph consisting of t internally disjoint paths of length n all sharing the same endpoints. As a corollary, for each fixed t ≥ 1 , R (θ n , t , θ n , t , C n t + λ) = (3 t + o (1)) n , where λ = 0 if nt is odd and λ = 1 if nt is even. In particular, we have R (C 2 n , C 2 n , C 2 n + 1) = (6 + o (1)) n , which is a special case of a result of Figaj and Łuczak (2018). [ABSTRACT FROM AUTHOR]

In this paper, we investigate a variant of Ramsey numbers called defective Ramsey numbers where cliques and independent sets are generalized to k-dense and k-sparse sets, both commonly called k-defective sets. We focus on the computation of defective Ramsey numbers restricted to some subclasses of perfect graphs. Since direct proof techniques are often insufficient for obtaining new values of defective Ramsey numbers, we provide a generic algorithm to compute defective Ramsey numbers in a given target graph class. We combine direct proof techniques with our efficient graph generation algorithm to compute several new defective Ramsey numbers in perfect graphs, bipartite graphs and chordal graphs. We also initiate the study of a related parameter, denoted by c k G (m) , which is the maximum order n such that the vertex set of any graph of order n in a class G can be partitioned into at most m subsets each of which is k-defective. We obtain several values for c k G (m) in perfect graphs and cographs. [ABSTRACT FROM AUTHOR]

Let T 1 , T 2 , … , T k be k (≥ 2) spanning trees of a graph G. The trees T 1 , T 2 , … , T k are completely independent if the paths connecting any two vertices of G in these k trees are pairwise internally disjoint. Sufficient conditions for a graph to possess k completely independent spanning trees have attracted popular attention intensively. In this paper, we focus on such sufficient conditions for bipartite graphs, and show that a bipartite graph G = (X ∪ Y , E) with order ν = m + n , m = | X | ≥ 2 k and n = | Y | ≥ m , has k completely independent spanning trees if for every pair of vertices x ∈ X , y ∈ Y , d (x) ≥ (k - 1) n k + 2 , d (y) ≥ (k - 1) m k + 2. Furthermore, we obtain that a bipartite graph G = (X ∪ Y , E) with order ν ≥ 8 , | X | ≥ 2 k and | Y | ≥ 2 k , has k completely independent spanning trees if the minimum degree δ (G) ≥ ⌊ (3 × 2 k - 2 - 1) ν 3 × 2 k - 1 ⌋ + 2 , or δ (G) ≥ (k - 1) ν 2 k + 2 and | X | = | Y |. [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]

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]

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]

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 this note we prove a new characterization of the derangement sets of Ferrers graphs and present a bijection between the derangement sets and F λ -Callan sequences. In particular, this connection reveals that the boolean numbers of the complete bipartite graphs are the D-relatives of poly-Bernoulli numbers. [ABSTRACT FROM AUTHOR]

An arc labeling ℓ of a directed graph G with positive integers is proper if for any two adjacent vertices v, u, we have S ℓ (v) ≠ S ℓ (u) , where S ℓ (v) denotes the sum of labels of the arcs with head v. The proper arc labeling number of a directed graph G, denoted by χ p → (G) , is min ℓ ∈ Γ max v ∈ V (G) S ℓ (v) , where Γ is the set of proper arc labelings of G. A proper arc labeling ℓ of G is optimal if max v ∈ V (G) S ℓ (v) = χ p → (G) . In this work we study the proper arc labeling number of graphs and present some lower and upper bounds. We show that every directed graph G has a (not necessarily optimal) proper arc labeling from { 1 , 2 , 3 } . So, Δ - (G) ≤ χ p → (G) ≤ 3 Δ - (G) , where Δ - (G) is the maximum incoming degree of vertices in G. Next, we prove that every graph G has an optimal proper arc labeling from { 1 , 2 , ... , r + 1 } , where r = max { ⌈ d G + (v) d G - (v) ⌉ + 1 : v ∈ V (G) } . Among other results, we show that if G is a bipartite graph, then Δ - (G) ≤ χ p → (G) ≤ Δ - (G) + 1 . Furthermore, we show that for each constant number c, there is a directed tree T such that it does not have any optimal proper arc labeling from { 1 , 2 , ... , c } . Next, we show that there is a polynomial time algorithm to find the proper arc labeling number of directed trees. On the other hand, we show that computing the proper arc labeling number of planar directed graphs is NP-hard. [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]

For graphs G and H, let G → k H signify that any k-edge coloring of G contains a monochromatic H as a subgraph. Let G (K 2 (N) , p) be random graph spaces with edge probability p, where K 2 (N) is the complete N × N bipartite graph. For a constant p ∈ (0 , 1 ] and a cycle C 2 n of length 2n, it is shown that Pr [ G (K 2 ((k + o (1)) n) , p) → k C 2 n ] → 1 as n → ∞ , where k = 2 , 3 . [ABSTRACT FROM AUTHOR]

The number Z (n) : = ⌊ n / 2 ⌋ ⌊ (n - 1) / 2 ⌋ is the smallest number of crossings in a simple planar drawing of K 2 , n in which both vertices on the 2-side have the same clockwise rotation. For two vertices u, v on the q-side of a simple drawing of K p , q , let cr D (u , v) denote the total number of crossings that edges incident with u have with edges incident with v. We show that in any simple drawing D of K p , q in a surface Σ the number of pairs of vertices on the q-side of K p , q having cr D (u , v) < Z (p) is bounded as a function of p and Σ . As a consequence, we also show that, for a fixed integer p and surface Σ , there exists a finite set of drawings D (p , Σ) of complete bipartite graphs such that, for each q, a crossing-minimal drawing of K p , q can be obtained by "duplicating vertices" in some drawing from D (p , Σ) . [ABSTRACT FROM AUTHOR]

A 2-edge-coloured graph G is supereulerian if G contains a spanning closed trail in which the edges alternate in colours. We show that for general 2-edge-coloured graphs it is NP-complete to decide whether the graph is supereulerian. An eulerian factor of a 2-edge-coloured graph is a collection of vertex-disjoint induced subgraphs which cover all the vertices of G such that each of these subgraphs is supereulerian. We give a polynomial algorithm to test whether a 2-edge-coloured graph has an eulerian factor and to produce one when it exists. A 2-edge-coloured graph is (trail-)colour-connected if it contains a pair of alternating (u, v)-paths ((u, v)-trails) whose union is an alternating closed walk for every pair of distinct vertices u, v. We prove that a 2-edge-coloured complete bipartite graph is supereulerian if and only if it is colour-connected and has an eulerian factor. A 2-edge-coloured graph is M-closed if xz is an edge of G whenever some vertex u is joined to both x and z by edges of the same colour. M-closed 2-edge-coloured graphs, introduced in Contreras-Balbuena et al. (Discret Math Theoret Comput Sci 21:1, 2019), form a rich generalization of 2-edge-coloured complete graphs. We show that if G is obtained from an M-closed 2-edge-coloured graph H by substituting independent sets for the vertices of H, then G is supereulerian if and only if G is trail-colour-connected and has an eulerian factor. Finally we discuss 2-edge-coloured complete multipartite graphs and show that such a graph may not be supereulerian even if it is trail-colour-connected and has an eulerian factor. [ABSTRACT FROM AUTHOR]

An edge-girth-regular e g r (v , k , g , λ) -graph Γ is a k-regular graph of order v and girth g in which every edge is contained in λ distinct g-cycles. Edge-girth-regularity is shared by several interesting classes of graphs which include edge- and arc-transitive graphs, Moore graphs, as well as many of the extremal k-regular graphs of prescribed girth or diameter. Infinitely many e g r (v , k , g , λ) -graphs are known to exist for sufficiently large parameters (k , g , λ) , and in line with the well-known Cage Problem we attempt to determine the smallest graphs among all edge-girth-regular graphs for given parameters (k , g , λ) . To facilitate the search for e g r (v , k , g , λ) -graphs of the smallest possible orders, we derive lower bounds in terms of the parameters k, g and λ . We also determine the orders of the smallest e g r (v , k , g , λ) -graphs for some specific parameters (k , g , λ) , and address the problem of the smallest possible orders of bipartite edge-girth-regular graphs. [ABSTRACT FROM AUTHOR]

We first introduce the class of bipartite absolute retracts with respect to tree obstructions with at most k leaves. Then, using the theory of homomorphism duality, we show that this class of absolute retracts coincides exactly with the bipartite graphs which admit a (k + 1) -ary near-unanimity polymorphism. This result mirrors the case for reflexive graphs and generalizes a known result for bipartite graphs which admit a 3-ary near-unanimity polymorphism. [ABSTRACT FROM AUTHOR]

The Maximum Weight Independent Set Problem (WIS) is a well-known NP-hard problem. A popular way to study WIS is to detect graph classes for which WIS can be solved in polynomial time, with particular reference to hereditary graph classes, i.e., defined by a hereditary graph property or equivalently by forbidding one or more induced subgraphs. Given two graphs G and H, G + H denotes the disjoint union of G and H. This manuscript shows that (i) WIS can be solved for ( P 4 + P 4 , Triangle)-free graphs in polynomial time, where a P 4 is an induced path of four vertices and a Triangle is a cycle of three vertices, and that in particular it turns out that (ii) for every ( P 4 + P 4 , Triangle)-free graph G there is a family S of subsets of V(G) inducing (complete) bipartite subgraphs of G, which contains polynomially many members and can be computed in polynomial time, such that every maximal independent set of G is contained in some member of S . These results seem to be harmonic with respect to other polynomial results for WIS on [subclasses of] certain S i , j , k -free graphs and to other structure results on [subclasses of] Triangle-free graphs. [ABSTRACT FROM AUTHOR]

A graph G is said to be distanced matchable if, for any matching M of G in which edges are pairwise at least distance d apart, there exists a perfect matching M ∗ of G which contains M. In this paper, we prove the following results: (i) if G is a cubic bipartite graph in which, for each e ∈ E (G) , there exist two cycles C 1 , C 2 of length at most d such that E (C 1) ∩ E (C 2) = { e } , then G is distance d - 1 matchable, and (ii) if G is a planar or projective planar cubic bipartite graph in which, for each e ∈ E (G) , there exist two cycles C 1 , C 2 of length at most 6 such that e ∈ E (C 1) ∩ E (C 2) , then G is distance 6 matchable. [ABSTRACT FROM AUTHOR]

For a graph G, define σ 2 (G) by σ 2 (G) = min { d G (x) + d G (y) : x , y ∈ V (G) , x ≠ y , x y ∉ E (G) } . If G is a bipartite graph with partite sets X and Y, we also define σ 1 , 1 (G) by σ 1 , 1 (G) = min { d G (x) + d G (y) : x ∈ X , y ∈ Y , x y ∉ E (G) } . Ore's theorem states that a graph of order n ≥ 3 with σ 2 (G) ≥ n contains a hamiltonian cycle and the Moon–Moser theorem states that a balanced bipartite graph G of order 2 n ≥ 4 with σ 1 , 1 (G) ≥ n + 1 contains a hamiltonian cycle. In Chen et al. (Discrete Math 343:Article No. 111663, 2020), we studied the relationship between Ore's theorem and the Moon–Moser theorem, and proved that the refinement of the Moon–Moser theorem given by Ferrara et al. (Discrete Math 312:459–461, 2012) implies Ore's theorem for graphs of even order. In this paper, we extend the above study to the graphs of odd order. Since no graphs of odd order contain a spanning balanced bipartite subgraph, the Moon–Moser theorem does not work in this case. We instead introduce its counterpart for the graphs in which the orders of the partite sets differ by 1, proved in Matsubara et al. (Discrete Math 340:87–95, 2017). We refine this result and prove that this refinement implies Ore's theorem. [ABSTRACT FROM AUTHOR]

An edge-colored graph is called rainbow (or heterochromatic) if all its edges have distinct colors. It is known that if an edge-colored connected graph H has minimum color degree at least |H|/2 and has a certain property, then H has a rainbow spanning tree. In this paper, we prove that if an edge-colored connected bipartite graph G has minimum color degree at least |G|/3 and has a certain property, then G has a rainbow spanning tree. We also give a similar sufficient condition for G to have a properly colored spanning tree. Moreover, we show that these minimum color-degree conditions are sharp. [ABSTRACT FROM AUTHOR]

In the Partition Into Complementary Subgraphs (Comp-Sub) problem we are given a graph G = (V , E) , and an edge set property Π , and asked whether G can be decomposed into two graphs, H and its complement H ¯ , for some graph H, in such a way that the edge cut-set (of the cut) [ V (H) , V (H ¯) ] satisfies property Π . Such a problem is motivated by the fact that several parameterized problems are trivially fixed-parameter tractable when the input graph G is decomposable into two complementary subgraphs. In addition, it generalizes the recognition of complementary prism graphs, and it is related to graph isomorphism when the desired cut-set is empty, Comp-Sub(∅ ). In this paper we are particularly interested in the case Comp-Sub(∅ ), where the decomposition also partitions the set of edges of G into E(H) and E (H ¯) . When the input is a chordal graph, we show that Comp-Sub(∅ ) is GI - complete , that is, polynomially equivalent to Graph Isomorphism. But it becomes more tractable than Graph Isomorphism for several subclasses of chordal graphs. We present structural characterizations for split, starlike, block, and unit interval graphs. We also obtain complexity results for permutation graphs, cographs, comparability graphs, co-comparability graphs, interval graphs, co-interval graphs and strongly chordal graphs. Furthermore, we present some remarks when Π is a general edge set property and the case when the cut-set M induces a complete bipartite graph. [ABSTRACT FROM AUTHOR]

It is well known that a graph is bipartite if and only if it contains no odd cycles. Gallai characterized edge colorings of complete graphs containing no properly colored triangles in recursive sense. In this paper, we completely characterize edge-colored complete graphs containing no properly colored odd cycles and give an efficient algorithm with complexity O (n 3) for deciding the existence of properly colored odd cycles in an edge-colored complete graph of order n. Moreover, we show that for two integers k, m with m ⩾ k ⩾ 3 , where k - 1 and m are relatively prime, an edge-colored complete graph contains a properly colored cycle of length ℓ ≡ k (mod m) if and only if it contains a properly cycle of length ℓ ′ ≡ k (mod m) , where ℓ ′ < 2 m 2 (k - 1) + 3 m . [ABSTRACT FROM AUTHOR]

A graph X is said to be chordal bipartite if it is bipartite and contains no induced cycle of length at least 6. It is proved that if X does not contain bipartite claw as an induced subgraph, then the Weisfeiler–Leman dimension of X is at most 3. This implies that the Weisfeiler–Leman dimension of any bipartite permutation graph is at most 3. The proof is based on the theory of coherent configurations. [ABSTRACT FROM AUTHOR]

A subgroup G of the automorphism group of a graph Γ acts half-arc-transitively on Γ if the natural actions of G on the vertex-set and edge-set of Γ are both transitive, but the natural action of G on the arc-set of Γ is not transitive. When G = Aut (Γ) the graph Γ is said to be half-arc-transitive. Given a bipartite cubic graph with a certain degree of symmetry two covering constructions that provide infinitely many tetravalent graphs admitting half-arc-transitive groups of automorphisms are introduced. Symmetry properties of constructed graphs are investigated. In the second part of the paper the two constructions are applied to the Heawood graph, the well-known incidence graph of the Fano plane. It is proved that the members of the infinite family resulting from one of the two constructions are all half-arc-transitive, and that the infinite family resulting from the second construction contains a mysterious family of arc-transitive graphs that emerged within the classification of tightly attached half-arc-transitive graphs of valence 4 back in 1998 and 2008. [ABSTRACT FROM AUTHOR]

The relation between Hamiltonicity and toughness of a graph is a long standing research problem. The paper studies the Hamiltonicity of the Cartesian product graph G 1 □ G 2 of graphs G 1 and G 2 satisfying that G 1 is traceable and G 2 is connected with a path factor. Let P n be the path of order n and H be a connected bipartite graph. With certain requirements of n, we show that the following three statements are equivalent: (i) P n □ H is Hamiltonian; (ii) P n □ H is 1-tough; and (iii) H has a path factor. [ABSTRACT FROM AUTHOR]

Given two graphs G and H, it is said that G percolates in H-bootstrap process if one could join all the nonadjacent pairs of vertices of G in some order such that a new copy of H is created at each step. Balogh, Bollobás and Morris in 2012 investigated the threshold of H-bootstrap percolation in the Erdős–Rényi model for the complete graph H and proposed the similar problem for H = K s , t , the complete bipartite graph. In this paper, we provide lower and upper bounds on the threshold of K 2 , t -bootstrap percolation. In addition, a threshold function is derived for K 2 , 4 -bootstrap percolation. [ABSTRACT FROM AUTHOR]

Let T be a tree with m edges. It was conjectured that every m-regular bipartite graph can be decomposed into edge-disjoint copies of T. In this paper, we prove that every 6-regular bipartite graph can be decomposed into edge-disjoint paths with 6 edges. As a consequence, every 6-regular bipartite graph on n vertices can be decomposed into n 2 paths, which is related to the well-known Gallai's Conjecture: every connected graph on n vertices can be decomposed into at most n + 1 2 paths. [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]

Let G = (V , E) be a finite connected graph along with a coloring of the vertices of G using the colors in a given set X. In this paper, we introduce multi-color forcing, a generalization of zero-forcing on graphs, and give conditions in which the multi-color forcing process terminates regardless of the number of colors used. We give an upper bound on the number of steps required to terminate a forcing procedure in terms of the number of vertices in the graph on which the procedure is being applied. We then focus on multi-color forcing with three colors and analyze the end states of certain families of graphs, including complete graphs, complete bipartite graphs, and paths, based on various initial colorings. We end with a few directions for future research. [ABSTRACT FROM AUTHOR]

An edge labeling of a connected graph G = (V , E) is said to be local antimagic if it is a bijection f : E → { 1 , ... , | E | } such that for any pair of adjacent vertices x and y, f + (x) ≠ f + (y) , where the induced vertex label f + (x) = ∑ f (e) , with e ranging over all the edges incident to x. The local antimagic chromatic number of G, denoted by χ la (G) , is the minimum number of distinct induced vertex labels over all local antimagic labelings of G. In this paper, we give counterexamples to the lower bound of χ la (G ∨ O 2) that was obtained in [Local antimagic vertex coloring of a graph, Graphs Combin. 33:275–285 (2017)]. A sharp lower bound of χ la (G ∨ O n) and sufficient conditions for the given lower bound to be attained are obtained. Moreover, we settled Theorem 2.15 and solved Problem 3.3 in the affirmative. We also completely determined the local antimagic chromatic number of complete bipartite graphs. [ABSTRACT FROM AUTHOR]

There have been researches on sufficient spectral conditions for Hamiltonian properties and path-coverable properties of graphs. Utilizing the Bondy–Chvátal closure, we provide a unified approach to study sufficient graph eigenvalue conditions for these properties and sharpen several former spectral Hamiltonian results on balanced bipartite graphs and complementary graphs. [ABSTRACT FROM AUTHOR]

Lepović gave a characterization of integral graphs of the form α K a , b ¯ in "On Integral Graphs Which Belong to the Class α K a , b ¯ " [Graphs Comb. 19, 527–532 (2003)]. However, for majority of the graphs α K a , b ¯ declared to be integral in this result, their spectrum also includes non-integer eigenvalues - 1 ± ab . Here we correct this result and indicate that integral graphs of this form are indeed very rare. [ABSTRACT FROM AUTHOR]

A bipartite-cylindrical drawing of the complete bipartite graph K m , n is a drawing on the surface of a cylinder, where the vertices are placed on the boundaries of the cylinder, one vertex-partition per boundary, and the edges do not cross the boundaries. The bipartite-cylindrical crossing number of K m , n , denoted by c r ⊚ (K m , n) , is the minimum number of crossings among all bipartite-cylindrical drawings of K m , n . This problem is equivalent to minimizing the number of crossings in drawings of K m , n in the plane where each of the vertex classes in the bipartition is placed on a circle and the edges do not cross the two circles. We determine c r ⊚ (K m , n) and give explicit constructions that achieve this number. This in turn gives an alternative proof to the Harary–Hill Conjecture restricted to a subclass of cylindrical drawings of the complete graph. [ABSTRACT FROM AUTHOR]

In this paper, we focus on a so-called Fan-type condition assuring us the existence of long paths in bipartite graphs. As a consequence of our main result, we completely determine the bipartite Ramsey numbers b (P s , B t 1 , t 2 ) , where B t 1 , t 2 is the graph obtained from a t 1 -star and a t 2 -star by joining their centers. [ABSTRACT FROM AUTHOR]

We study a combinatorial coloring game between two players, Spoiler and Painter, who alternate turns. First, Spoiler places a new token at a vertex in G, and Painter responds by assigning a color to the new token. Painter must ensure that tokens on the same or adjacent vertices receive distinct colors. Spoiler must ensure that the token graph (in which two tokens are adjacent if and only if their distance in G is at most 1) has chromatic number at most w. Painter wants to minimize the number of colors used, and Spoiler wants to force as many colors as possible. Let f (w , G) be the minimum number of colors needed in an optimal Painter strategy. The game is motivated by a natural online coloring problem on the real line which remains open. A graph G is token-perfect if f (w , G) = w for each w. We show that a graph is token-perfect if and only if it can be obtained from a bipartite graph by cloning vertices. We also give a forbidden induced subgraph characterization of the class of token-perfect graphs, which may be of independent interest. When G is not token-perfect, determining f (w , G) seems challenging; we establish f (w , G) asymptotically for some of the minimal graphs that are not token-perfect. [ABSTRACT FROM AUTHOR]

Finding the multiplicity of cycles in bipartite graphs is a fundamental problem of interest in many fields including the analysis and design of low-density parity-check (LDPC) codes. Recently, Blake and Lin computed the number of shortest cycles (g-cycles, where g is the girth of the graph) in a bi-regular bipartite graph, in terms of the degree sequences and the spectrum (eigenvalues of the adjacency matrix) of the graph (Blake and Lin in IEEE Trans Inf Theory 64(10): 6526–6535, 2018). This result was subsequently extended in Dehghan and Banihashemi (IEEE Trans Inf Theory 65(6):3778–3789, 2019) to cycles of length g + 2 , ... , 2 g - 2 , in bi-regular bipartite graphs, as well as 4-cycles and 6-cycles in irregular and half-regular bipartite graphs, with g ≥ 4 and g ≥ 6 , respectively. In this paper, we complement these positive results with negative results demonstrating that the information of the degree sequences and the spectrum of a bipartite graph is, in general, insufficient to count (a) the i-cycles, i ≥ 2 g , in bi-regular graphs, (b) the i-cycles for any i > g , regardless of the value of g, and g-cycles for g ≥ 6 , in irregular graphs, and (c) the i-cycles for any i > g , regardless of the value of g, and g-cycles for g ≥ 8 , in half-regular graphs. To obtain these results, we construct counter-examples using the Godsil–McKay switching. [ABSTRACT FROM AUTHOR]

In this paper we construct a class of bounded degree bipartite graphs with a small separator and large bandwidth, thereby showing that separability and bandwidth are not linearly equivalent. Furthermore, we also prove that graphs from this class are spanning subgraphs of graphs with minimum degree just slightly above n / 2, even though their bandwidth is large. [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]

In this paper, a formula for the Ihara zeta function of the cone over a semiregular bipartite graph is derived. Using this formula, we show that two cones over semiregular bipartite graphs are cospectral if and only if they have the same Ihara zeta function. Moreover, the convergence of the zeta function of this family of graphs is considered. [ABSTRACT FROM AUTHOR]

A dominating set of a graph G is a set D ⊆ V G such that every vertex in V G - D is adjacent to at least one vertex in D, and the domination number γ (G) of G is the minimum cardinality of a dominating set of G. In this paper we provide a new characterization of bipartite graphs whose domination number is equal to the cardinality of its smaller partite set. Our characterization is based upon a new graph operation. [ABSTRACT FROM AUTHOR]

Indicated coloring is a type of game coloring in which two players collectively color the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent the realization of this project. The smallest number of colors necessary for Ann to win the game on a graph G (regardless of Ben's strategy) is called the indicated chromatic number of G, denoted by χ i (G) . In this paper, we obtain structural characterization of { P 5 , K 4 , K i t e , B u l l } -free graphs and connected { P 6 , C 5 , K 1 , 3 } -free graphs that contain an induced C 6 . Also, we prove that { P 5 , K 4 , K i t e , B u l l } -free graphs and connected { P 6 , C 5 , P 5 ¯ , K 1 , 3 } -free graphs which contain an induced C 6 are k-indicated colorable for all k ≥ χ (G) . In addition, we show that, if m ≥ 1 and G is a bipartite graph, then χ i (K [ G ] (m , m , ... , m)) = χ (K [ G ] (m , m , ... , m)) . Further, we show that K [ C 5 ] is k-indicated colorable for all k ≥ χ (G) and as a consequence, we exhibit that { P 2 ∪ P 3 , C 4 } -free graphs, { P 5 , C 4 } -free graphs are k-indicated colorable for all k ≥ χ (G) . This partially answers one of the questions which was raised by Grzesik (Discret Math 312:3467–3472, 2012). [ABSTRACT FROM AUTHOR]

A subgraph H of an edge-colored graph G is rainbow if all of its edges have different colors. The anti-Ramsey number is the maximum number of colors in an edge-coloring of G with no rainbow copy of H. Originally a complete graph was considered as G. In this paper, we consider a complete bipartite graph as the host graph and discuss some results for the graph H being hamiltonian cycle and perfect matching. Let c (K p , p , t) and m (K p , p , t) be the maximum number of colors in an edge-coloring of the complete bipartite graph K p , p not having t edge-disjoint rainbow hamiltonian cycles and perfect matchings, respectively. We prove that c (K p , p , t) = p 2 - p + t for t ≥ 2 , p ≥ 4 t - 1 and m (K p , p , t) = p 2 - 2 p + t + 1 for t ≥ 2, p ≥ 2 t + 8 . [ABSTRACT FROM AUTHOR]

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number of G, denoted by i(G), is the minimum cardinality of an independent dominating set. In this paper, we study the following conjecture posed by Goddard and Henning (Discrete Math. 313:839–854, 2013): If G ≇ K 3 , 3 is a connected, cubic, bipartite graph on n vertices, then i (G) ≤ 4 11 n . Henning et al. (Discrete Appl. Math. 162:399–403, 2014) prove the conjecture when the girth is at least 6. In this paper we strengthen this result by proving the conjecture when the graph has no subgraph isomorphic to K 2 , 3 . [ABSTRACT FROM AUTHOR]

Let G be a plane elementary bipartite graph with more than one finite face. We first characterize forcing edges and anti-forcing edges of G in terms of handles and forcing faces. We then introduce the concept of a nice pair of faces of G, which allows us to provide efficient algorithms to construct plane minimal elementary bipartite graphs from G. We show that if G ′ is a minimal elementary spanning subgraph of G, then all vertices of a forcing face of G are contained in a forcing face of G ′ , and any forcing face of G is a forcing face of G ′ if it is still a face of G ′ . Furthermore, any forcing edge (resp., anti-forcing edge) of G is still a forcing edge (resp., an anti-forcing edge) of G ′ if it is still an edge of G ′ . We conclude the paper with the co-existence property of forcing edges and anti-forcing edges for those plane minimal elementary bipartite graphs that remain 2-connected when any handle of length one (if exists) is deleted. [ABSTRACT FROM AUTHOR]

In 1957 Hugo Steinhaus published an elementary, recreational problem concerning a configuration of rooks on the chessboard (Steinhaus in Matematyka, czasopismo dla nauczycieli 1:55, 1957). Over the last 60 years, this problem has achieved quite a peculiar status: apparently, it had two (both published) solutions—one short and elegant (Steinhaus in Sto zadań [One Hundred Problems], PWN, Warszawa, 1958), but (as it soon turned out) incorrect (Zadania konkursowe, Rozwiązania [Competition problems, Solutions]. Matematyka, Czasopismo dla nauczycieli 4-6:62-65, 1958); while the other (Zadania konkursowe, 1958) (Steinhaus in One Hundred Problems in Elementary Mathematics. Popular Lectures in Mathematics, Pergamon Press, Oxford and PWN, Warszawa, 1963)—known internationally, yet long and complex, so probably never read (except, perhaps, by its author) and never checked for its correctness. It was only in 2004 when a correct and short solution of the original Steinhaus' problem was found and published (Morawiec in Matematyka Czasopismo dla nauczycieli 2:46-50, 2004). The solution involved the well-known Hall's 'marriage' theorem (Wilson in Introduction to Graph Theory, Longman, Harlow, 1996, p. 113). Further investigation has shown that the connection between Steinhaus' problem and Hall's theorem runs deeper than the use of the latter in the solution of the former. In this paper we present the results of this investigation, by the way defining a simple but seemingly new class of special matchings (ibid.) in bipartite graphs (id., p. 18). [ABSTRACT FROM AUTHOR]