Search

We consider the classic budgeted maximum weight independent set (BMWIS) problem. The input is a graph G = (V , E) , where each vertex v ∈ V has a weight w (v) and a cost c (v) , and a budget B. The goal is to find an independent set S ⊆ V in G such that ∑ v ∈ S c (v) ≤ B , which maximizes the total weight ∑ v ∈ S w (v). Since the problem on general graphs cannot be approximated within ratio | V | 1 − ɛ for any ɛ > 0 , BMWIS has attracted significant attention on graph families for which a maximum weight independent set can be computed in polynomial time. Two notable such graph families are bipartite and perfect graphs. BMWIS is known to be NP-hard on both of these graph families; however, prior to this work, the best possible approximation guarantees for these graphs were wide open. In this paper, we give a tight 2-approximation for BMWIS on perfect graphs and bipartite graphs. In particular, we give a (2 − ɛ) lower bound for BMWIS on bipartite graphs, already for the special case where the budget is replaced by a cardinality constraint, based on the Small Set Expansion Hypothesis (SSEH). For the upper bound, we design a 2-approximation for BMWIS on perfect graphs using a Lagrangian relaxation based technique. Finally, we obtain a tight lower bound for the capacitated maximum weight independent set (CMWIS) problem, the special case of BMWIS where w (v) = c (v) ∀ v ∈ V. We show that CMWIS on bipartite and perfect graphs is unlikely to admit an efficient polynomial-time approximation scheme (EPTAS). Thus, the existing PTAS for CMWIS is essentially the best we can expect. [ABSTRACT FROM AUTHOR]

Let i be a positive integer, an i -star denoted by S i is a complete bipartite graph K 1 , i. An { S 2 , S 3 } -packing of a graph G is a collection of vertex-disjoint subgraphs of G in which each subgraph is a 2-star or a 3-star. The maximum { S 2 , S 3 } -packing problem is to find an { S 2 , S 3 } -packing of a given graph containing the maximum number of vertices. The { S 2 , S 3 } -factor problem is to answer whether there is an { S 2 , S 3 } -packing containing all vertices of the given graph. The { S 2 , S 3 } -factor problem is NP-complete in cubic graphs. In this paper we design a quadratic-time algorithm for finding an { S 2 , S 3 } -packing of G that covers at least thirteen-sixteenths of its vertices with only a few exceptions. We also present some (2 , 3) -regular graphs with their maximum { S 2 , S 3 } -packings covering exactly thirteen-sixteenths of their vertices. [ABSTRACT FROM AUTHOR]

The classical extremal function for a graph H , ex (K n , H) is the largest number of edges in a subgraph of K n that contains no subgraph isomorphic to H. Note that defining ex (K n , H − ind) by forbidding induced subgraphs isomorphic to H is not very meaningful for a non-complete H since one can avoid it by considering a clique. For graphs F and H , let ex (K n , { F , H − ind }) be the largest number of edges in an n -vertex graph that contains no subgraph isomorphic to F and no induced subgraph isomorphic to H. Determining this function asymptotically reduces to finding either ex (K n , F) or ex (K n , H) , unless H is a biclique or both F and H are bipartite. Here, we consider the bipartite setting, ex (K n , n , { F , H − ind }) when K n is replaced with K n , n , F is a biclique, and H is a bipartite graph. Our main result, a strengthening of a result by Sudakov and Tomon, implies that for any d ≥ 2 and any K d , d -free bipartite graph H with each vertex in one part of degree either at most d or a full degree, so that there are at most d − 2 full degree vertices in that part, one has ex (K n , n , { K t , t , H − ind }) = o (n 2 − 1 / d). This provides an upper bound on the induced Turán number for a wide class of bipartite graphs and implies in particular an extremal result for bipartite graphs of bounded VC-dimension by Janzer and Pohoata. [ABSTRACT FROM AUTHOR]

An edge-coloured path is monochromatic if all of its edges have the same colour. For a k -connected graph G , the monochromatic k -connection number of G , denoted by m c k (G) , is the maximum number of colours in an edge-colouring of G such that, any two vertices are connected by k internally vertex-disjoint monochromatic paths. In this paper, we shall study the parameter m c k (G). We obtain bounds for m c k (G) , for general graphs G. We also compute m c k (G) exactly when k is small, and G is a graph on n vertices, with a spanning k -connected subgraph having the minimum possible number of edges, namely ⌈ k n 2 ⌉. We prove a similar result when G is a bipartite graph. [ABSTRACT FROM AUTHOR]

A bipartite graph G is two-disjoint-cycle-cover edge [ r 1 , r 2 ] -bipancyclic if, for any vertex-disjoint edges u v and x y in G and any even integer ℓ satisfying r 1 ⩽ ℓ ⩽ r 2 , there exist vertex-disjoint cycles C 1 and C 2 such that | V (C 1) | = ℓ , | V (C 2) | = | V (G) | − ℓ , u v ∈ E (C 1) and x y ∈ E (C 2). In this paper, we prove that the n -star graph S n is two-disjoint-cycle-cover edge [ 6 , n ! 2 ] -bipancyclic for n ⩾ 5 , and thus it is two-disjoint-cycle-cover vertex [ 6 , n ! 2 ] -bipancyclic for n ⩾ 5. Additionally, it is examined that S n is two-disjoint-cycle-cover [ 6 , n ! 2 ] -bipancyclic for n ⩾ 4. [ABSTRACT FROM AUTHOR]

Given a graph G , a subset of vertices is called a maximum dissociation set of G if it induces a subgraph with vertex degree at most 1, and the subset has maximum cardinality. The cardinality of a maximum dissociation set is called the dissociation number of G. The adjacency matrix and the degree diagonal matrix of G are denoted by A (G) and D (G) , respectively. In 2017, Nikiforov proposed the A α -matrix: A α (G) = α D (G) + (1 − α) A (G) , where α ∈ [ 0 , 1 ]. The largest eigenvalue of this novel matrix is called the A α -index of G. In this paper, we firstly determine the connected graph (resp. bipartite graph, tree) having the largest A α -index over all connected graphs (resp. bipartite graphs, trees) with fixed order and dissociation number. Secondly, we describe the structure of all the n -vertex graphs having the minimum A α -index with dissociation number τ , where τ ⩾ ⌈ 2 3 n ⌉. Finally, we identify all the connected n -vertex graphs with dissociation number τ ∈ { 2 , ⌈ 2 3 n ⌉ , n − 1 , n − 2 } having the minimum A α -index. [ABSTRACT FROM AUTHOR]

A bisection of a graph is a bipartition of its vertex set in which the two parts differ in size by at most 1, and its size is the number of edges which across the two parts. Let G be a graph with n vertices, m edges and degree sequence d 1 , d 2 , ... , d n . Motivated by a few classical results on Max-Cut of graphs, Lin and Zeng proved that if G is { C 4 , C 6 } -free and has a perfect matching, then G has a bisection of size at least m / 2 + Ω (∑ i = 1 n d i ) , and conjectured the same bound holds for C 4 -free graphs with perfect matchings. In this paper, we confirm the conjecture under the additional condition that G is C 5 -free. [ABSTRACT FROM AUTHOR]

A matching in a graph is a set of pairwise nonadjacent edges. Denote by m (G , k) the number of matchings of cardinality k in a graph G. A quasi-order ⪯ is defined by G ⪯ H whenever m (G , k) ≤ m (H , k) holds for all k. Let BG 1 (n , γ) be the set of connected bipartite graphs with n vertices and γ cut vertices, and BG 2 (n , γ) be the set of connected bipartite graphs with n vertices and γ cut edges. We determine the greatest and least elements with respect to this quasi-order in BG 1 (n , γ) and the greatest element in BG 2 (n , γ) for all values of n and γ. As corollaries, we find that these graphs maximize (resp. minimize) the Hosoya index and the matching energy within the respective sets. [ABSTRACT FROM AUTHOR]

Consider a graph G = (V , E) and a function f : V → { 0 , 1 , 2 }. A vertex u with f (u) = 0 is defined as undefended by f if it lacks adjacency to any vertex with a positive f -value. The function f is said to be a weak Roman dominating function (WRD function) if, for every vertex u with f (u) = 0 , there exists a neighbor v of u with f (v) > 0 and a new function f ′ : V → { 0 , 1 , 2 } defined in the following way: f ′ (u) = 1 , f ′ (v) = f (v) − 1 , and f ′ (w) = f (w) , for all vertices w in V ∖ { u , v } ; so that no vertices are undefended by f ′. The total weight of f is equal to ∑ v ∈ V f (v) , and is denoted as w (f). The Weak Roman domination number denoted by γ r (G) , represents m i n { w (f) | f is a WRD function of G }. For a given graph G , the problem of finding a WRD function of weight γ r (G) is defined as the Minimum Weak Roman domination problem. The problem is already known to be NP-hard for bipartite and chordal graphs. In this paper, we further study the algorithmic complexity of the problem. We prove the NP-hardness of the problem for star convex bipartite graphs and comb convex bipartite graphs, which are subclasses of bipartite graphs. In addition, we show that for the bounded degree star convex bipartite graphs, the problem is efficiently solvable. We also prove the NP-hardness of the problem for split graphs, a subclass of chordal graphs. On the positive side, we present a polynomial-time algorithm to solve the problem for P 4 -sparse graphs. Further, we have presented some approximation results. [ABSTRACT FROM AUTHOR]

A connected matching in a graph G consists of a set of pairwise disjoint edges whose covered vertices induce a connected subgraph of G. While finding a connected matching of maximum cardinality is a well-solved problem, it is NP-hard to determine an optimal connected matching in an edge-weighted graph, even in the planar bipartite case. We present two mixed integer programming formulations and a sophisticated branch-and-cut scheme to find weighted connected matchings in general graphs. The formulations explore different polyhedra associated to this problem, including strong valid inequalities both from the matching polytope and from the connected subgraph polytope. We conjecture that one attains a tight approximation of the convex hull of connected matchings using our strongest formulation, and report encouraging computational results over DIMACS Implementation Challenge benchmark instances. The source code of the complete implementation is also made available. [ABSTRACT FROM AUTHOR]

In 1964, Moon extended Cayley's formula to a nice expression of the number of spanning trees in complete graphs containing any fixed spanning forest. After nearly 60 years, Dong and the first author discovered the second Moon-type formula: an explicit formula of the number of spanning trees in complete bipartite graphs containing any fixed spanning forest. Followed this direction, Li, Chen and Yan found the Moon-type formula for complete 3- and 4-partite graphs. These are the only families of graphs that have the corresponding Moon-type formulas. In this paper, we first determine resistance distances in the vertex-weighted complete split graph S m , n ω. Then we obtain the Moon-type formula for the vertex-weighted complete split graph S m , n ω , that is, the weighted spanning tree enumerator of S m , n ω containing any fixed spanning forest. [ABSTRACT FROM AUTHOR]

The median function is a location/consensus function that maps any profile π (a finite multiset of vertices) to the set of vertices that minimize the distance sum to vertices from π. The median function satisfies several simple axioms: Anonymity (A), Betweeness (B), and Consistency (C). McMorris, Mulder, Novick and Powers (2015) defined the ABC-problem for consensus functions on graphs as the problem of characterizing the graphs (called, ABC-graphs) for which the unique consensus function satisfying the axioms (A), (B), and (C) is the median function. In this paper, we show that modular graphs with G 2 -connected medians (in particular, bipartite Helly graphs) are ABC-graphs. On the other hand, the addition of some simple local axioms satisfied by the median function in all graphs (axioms (T), and (T 2)) enables us to show that all graphs with connected median (comprising Helly graphs, median graphs, basis graphs of matroids and even Δ -matroids) are ABCT-graphs and that benzenoid graphs are ABCT 2 -graphs. McMorris et al (2015) proved that the graphs satisfying the pairing property (called the intersecting-interval property in their paper) are ABC-graphs. We prove that graphs with the pairing property constitute a proper subclass of bipartite Helly graphs and we discuss the complexity status of the recognition problem of such graphs. [ABSTRACT FROM AUTHOR]

Given a graph G without isolated vertices, a function f : V (G) → { 0 , 1 , 2 } is a covering total Italian dominating function if (i) the set of vertices labeled with 0 forms an independent set; (ii) every vertex labeled with 0 is adjacent to two vertices labeled with 1 or to one vertex labeled with 2; and (iii) the set of vertices labeled with 1 or 2 forms a total dominating set. The covering total Italian domination number of G is the smallest possible value of the sum ∑ v ∈ V (G) f (v) among all possible covering total Italian dominating functions f on V (G). The concepts above are introduced in this article, and the study of its combinatorial and computational properties is initiated. Specifically, we show several relationships between such parameter and other domination related parameters in graphs. We also prove the NP-completeness of the related decision problem for bipartite graphs, and present some approximation results on computing our parameter. In addition, we compute the exact value of the covering total Italian domination number of some graphs with emphasis on some Cartesian products. [ABSTRACT FROM AUTHOR]

In this paper we study the class of graphs G m , n that have the same degree sequence as two disjoint cliques K m and K n , as well as the class G ¯ m , n of the complements of such graphs. We establish various properties of G m , n and G ¯ m , n related to recognition, connectivity, diameter, bipartiteness, Hamiltonicity, and pancyclicity. We also show that several classical optimization problems on these graphs are NP-hard, while others can be solved efficiently. [ABSTRACT FROM AUTHOR]

Let D = (V , A) be a digraph of order n , S a subset of V of size k , where k is a positive integer and 2 ≤ k ≤ n. A directed cycle C of D is called a directed S -Steiner cycle (or, an S -cycle for short) if S ⊆ V (C). Steiner cycles have applications in the optimal design of reliable telecommunication and transportation networks. A pair of S -cycles is called internally disjoint if they have no common arc and the common vertex set of them is exactly S. Let κ S c (D) be the maximum number of pairwise internally disjoint S -cycles in D. The directed cycle k -connectivity of D is defined as κ k c (D) = min κ S c (D) ∣ S ⊆ V (D) , S = k , 2 ≤ k ≤ n. In this paper, we study the directed cycle k -connectivity of complete digraphs K ↔ n and complete regular bipartite digraphs K ↔ a , a. We give a sharp lower bound for κ k c ( K ↔ n) and determine the exact values for κ k c ( K ↔ n) when k ∈ { 2 , 3 , 4 , 6 }. We also determine the exact value of κ k c ( K ↔ a , a) for each 2 ≤ k ≤ n. [ABSTRACT FROM AUTHOR]

A graph G = ({ 1 , 2 , ... , n } , E) is 12- representable if there is a word w over { 1 , 2 , ... , n } such that two vertices i and j with i < j are adjacent if and only if every j occurs before every i in w. These graphs have been shown to be equivalent to the complements of simple-triangle graphs. This equivalence provides a characterization in terms of forbidden patterns in vertex orderings as well as a polynomial-time recognition algorithm. The class of 12-representable graphs was introduced by Jones et al. (2015) as a variant of word-representable graphs. A general research direction for word-representable graphs suggested by Kitaev and Lozin (2015) is to study graphs representable by some specific types of words. For instance, Gao, Kitaev, and Zhang (2017) and Mandelshtam (2019) investigated word-representable graphs defined by pattern-avoiding words. Following this research direction, this paper studies 12-representable graphs defined by words that avoid a pattern p. Such graphs are trivial when p is of length 2. When p = 111, 121, 231, and 321, the classes of such graphs are equivalent to well-known classes, such as trivially perfect graphs and bipartite permutation graphs. For the cases where p = 123, 132, and 211, this paper provides forbidden pattern characterizations. • Classes of graphs 12-representable by pattern-avoiding words are introduced. • Among such classes, those with patterns of length at most 3 are investigated. • Some classes are equivalent to well-known classes such as trivially perfect graphs. • Forbidden pattern characterizations are provided for other classes. [ABSTRACT FROM AUTHOR]

We consider one variant of stable assignment problems in a bipartite graph endowed with nonnegative capacities on the edges and quotas on the vertices. It can be viewed as a generalization of the stable allocation problem introduced by Baïou and Balinsky, which arises when strong linear orders of preferences on the vertices in the latter are replaced by weak ones. At the same time, our stability problem can be stated in the framework of a theory by Alkan and Gale on stable schedule matchings generated by choice functions of a wide scope. In our case, the choice functions are of a special, so-called mixed , type. The main content of this paper is devoted to a study of rotations in our mixed model, functions on the edges determining "elementary" transformations between close stable assignments. These look more sophisticated compared with rotations in the stable allocation problem (which are generated by simple cycles). We efficiently construct a poset of rotations and show that the stable assignments are in bijection with the so-called closed functions for this poset; this gives rise to a "compact" affine representation for the lattice of stable assignments and leads to an efficient method to find a stable assignment of minimum cost. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph where V and E are the vertex and edge sets, respectively. For two disjoint subsets A and B of V , we say A dominates B if every vertex of B is adjacent to at least one vertex of A. A vertex partition π = { V 1 , V 2 , ... , V k } of G is called a transitive partition of size k if V i dominates V j for all 1 ≤ i < j ≤ k. In this article, we study a variation of transitive partition, namely 2- transitive partition. For two disjoint subsets A and B of V , we say A 2- dominates B if every vertex of B is adjacent to at least two vertices of A. A vertex partition π = { V 1 , V 2 , ... , V k } of G is called a 2- transitive partition of size k if V i 2 -dominates V j for all 1 ≤ i < j ≤ k. The Maximum 2- Transitivity Problem is to find a 2 -transitive partition of a given graph with the maximum number of parts. We show that the decision version of this problem is NP-complete for chordal and bipartite graphs. On the positive side, we design three linear-time algorithms for solving Maximum 2- Transitivity Problem in trees, split, and bipartite chain graphs. [ABSTRACT FROM AUTHOR]

The extremal problem of two types of high order spectra for graphs are considered, which are called r -adjacency spectrum and t -clique spectrum, respectively. In this paper, we obtain the maximum r -adjacency spectral radius of a K r + 1 minor-free graph of order n in the case 1 ≤ r ≤ 3 , which implies the Hadwiger's conjecture is true for 1 ≤ r ≤ 3. Moreover, an upper bound of the 3-clique spectral radius of a B k -free and K 2 , l -free graph G of order n is given, where B k is the graph consisting of k triangles sharing an edge. As a corollary of this result, we obtain an upper bound of the number of the triangles for G which improves a result of Alon and Shikhelman (2016). [ABSTRACT FROM AUTHOR]

In 2010, Butler introduced the unfolding operation on a bipartite graph to produce two bipartite graphs, which are cospectral for the adjacency and the normalized Laplacian matrices. In this article, we describe how the idea of unfolding a bipartite graph with respect to another bipartite graph can be extended to nonbipartite graphs. In particular, we describe how unfoldings involving reflexive bipartite, semi-reflexive bipartite, and multipartite graphs are used to obtain cospectral nonisomorphic graphs for the adjacency matrix. [ABSTRACT FROM AUTHOR]

Let G be a graph and k be a positive integer, and let Kc (G , k) denote the number of Kempe equivalence classes for the k -colorings of G. In 2006, Mohar noted that Kc (G , k) = 1 if G is bipartite. As a generalization, we show that Kc (G , k) = 1 if G is formed from a bipartite graph by adding any number of edges less than ⌈ k / 2 ⌉ 2 + ⌊ k / 2 ⌋ 2 . We show that our result is tight (up to lower order terms) by constructing, for each k ≥ 8 , a graph G formed from a bipartite graph by adding (k 2 + 8 k − 45 + 1) / 4 edges such that Kc (G , k) ≥ 2. This refutes a recent conjecture of Higashitani–Matsumoto. [ABSTRACT FROM AUTHOR]

Fix a positive integer n and consider the bipartite graph whose vertices are the 3-element subsets and the 2-element subsets of [ n ] = { 1 , 2 , ... , n } , and there is an edge between A and B if A ⊂ B. We prove that the domination number of this graph is n 2 − ⌊ (n + 1) 2 8 ⌋ , we characterize the dominating sets of minimum size, and we observe that the minimum size dominating set can be chosen as an independent set. This is an exact version of an asymptotic result by Balogh, Katona, Linz and Tuza (2021). For the corresponding bipartite graph between the (k + 1) -element subsets and the k -element subsets of [ n ] (k ⩾ 3), we provide a new construction for small independent dominating sets. This improves on a construction by Gerbner, Kezegh, Lemons, Palmer, Pálvölgyi and Patkós (2012), who studied these independent dominating sets under the name saturating flat antichains. [ABSTRACT FROM AUTHOR]

Let π = (f 1 , ... , f m ; g 1 , ... , g n) , where f 1 , ... , f m and g 1 , ... , g n are two nonincreasing sequences of nonnegative integers. The pair π = (f 1 , ... , f m ; g 1 , ... , g n) is said to be a bigraphic pair if there is a simple bipartite graph G [ X , Y ] with vertex bipartition (X , Y) such that f 1 , ... , f m and g 1 , ... , g n are the degrees of the vertices in X and Y , respectively. In this case, G is referred to as a realization of π. For a given bipartite graph H = H [ X , Y ] with | X | = s and | Y | = t , we say that π is a potentially H -bigraphic pair if π has a realization G containing H as a subgraph with the s vertices of X in the part of G of size m and the t vertices of Y in the part of G of size n. Let σ (H , m , n) denote the minimum integer k such that every bigraphic pair π = (f 1 , ... , f m ; g 1 , ... , g n) with σ (π) ≥ k is a potentially H -bigraphic pair, where σ (π) = f 1 + ⋯ + f m . The parameter σ (H , m , n) is known as the potential function of H , and can be viewed as a degree sequence variant of the classical extremal function e x (H , m , n) as introduced by Erdős et al. Ferrara et al. determined σ (K s , t , m , n) for n ≥ m ≥ 9 s 4 t 4 , σ (P ℓ , m , n) for n ≥ m ≥ ⌈ ℓ 2 ⌉ and σ (C 2 t , m , n) for n ≥ m ≥ 2 (t + 1). In this paper, for an arbitrary bipartite graph H , we firstly give a construction that yields a lower bound on σ (H , m , n). Then, we determine σ (A s , t d , m , n) for n ≥ 2 s 2 t 2 , where A s , t d is the graph obtained from K s − 1 , t by adding a new vertex that is adjacent to d vertices of the part of size t. Finally, we investigate the precise behavior of σ (H , m , n) for an arbitrary bipartite graph H , and determine σ (H , m , n) for n ≥ max { m (t − d) + (s − 1) (d − 1) , 2 s 2 t 2 } , where d = min { d H (x) | x ∈ X }. [ABSTRACT FROM AUTHOR]

In a graph G = (V , E) , a non-empty set A of k distinct vertices, is called a k - attack on G. The vertices in the set A are considered to be under attack. A set D ⊆ V can defend or counter the attack A on G if there exists a one-to-one function f : A ⟼ D , such that either f (u) = u or there is an edge between u , and its image f (u) , in G. A set D is called a k - defensive dominating set if it defends against any k -attack on G. Given a graph G = (V , E) , the minimum k -defensive domination problem requires us to compute a minimum cardinality k -defensive dominating set of G. When k is not fixed, it is co-NP-hard to decide if D ⊆ V is a k -defensive dominating set. However, when k is fixed, the decision version of the problem is NP-complete for general graphs. On the positive side, the problem can be solved in linear time when restricted to paths, cycles, co-chain, and threshold graphs for any k. This paper mainly focuses on the problem when k > 0 is fixed. We prove that the decision version of the problem remains NP-complete for bipartite graphs; this answers a question asked by Ekim et al. (Discrete Math. 343 (2) (2020)). We establish a lower and upper bound on the approximation ratio for the problem. Further, we show that the minimum k -defensive domination problem is APX-complete for bounded degree graphs. On the positive side, we show that the problem is efficiently solvable for complete bipartite graphs for any k > 0. Towards the end, we study a relationship between the defensive domination number and another well-studied domination parameter. [ABSTRACT FROM AUTHOR]

The normalized algebraic connectivity of a graph with order n , denoted by ρ n − 1 , is the second smallest eigenvalue of the normalized Laplacian matrix of the graph. In this paper, we determine the graphs with ρ n − 1 ≥ 3 n − 8 3 n − 9 by using forbidden subgraph characterization. A stronger result on bipartite graph is also obtained. [ABSTRACT FROM AUTHOR]

A bipartite graph G = (A , B , E) is said to be a biconvex bipartite graph if there exist orderings < A in A and < B in B such that the neighbors of every vertex in A are consecutive with respect to < B and the neighbors of every vertex in B are consecutive with respect to < A. A caterpillar is a tree that will result in a path upon deletion of all the leaves. In this paper, we prove that there exists a spanning caterpillar in any connected biconvex bipartite graph. Besides being interesting on its own, this structural result has other consequences. For instance, this directly resolves the burning number conjecture for biconvex bipartite graphs. [ABSTRACT FROM AUTHOR]

Let B n denote the family of all maximal bipartite planar graphs on n vertices. Given a family of graphs H , let B n (H) denote the family of all maximal bipartite planar graphs on n vertices which are not H -free. For graph G and a family of graphs H , if G is not H -free, the rainbow number of H in G , denoted by r b (G , H) , is the minimum positive integer t , such that any t -edge-colored graph G contains a rainbow copy of some graph in H. The rainbow number of H in maximal bipartite planar graph, denoted by r b (B n (H) , H) , is defined as max { r b (G , H) | G ∈ B n (H) }. A cycle on l vertices is denoted by C l. The graph obtained by arbitrarily adding one pendant edge at one vertex of a cycle C l is denoted by C l +. For any positive integer k , let C k ≔ { C 4 , C 6 , ... , C 2 k + 2 } and C k , 2 i 0 + ≔ (C k ∖ { C 2 i 0 }) ∪ { C 2 i 0 + } for some i 0 ∈ { 2 , 3 , ... , k + 1 }. In this paper, we firstly prove that r b (B n , C k) = r b (B n , C k , 2 i 0 +) = n + n − 2 k + 2 − 1 for any n ≥ max { 2 k + 2 , 5 } and k + 1 ≥ i 0 ≥ 2. We then obtain that r b (B n (H) , H) = 2 n − 4 for any n ≥ | V (H) | and k ≥ 3 , where H ∈ { C 2 k , C 2 k + }. [ABSTRACT FROM AUTHOR]

In this paper, based on the Diophantine equation technique, we first prove the circulant graph C (Z n , { k 1 , k 2 }) is isomorphic to the disjoint union of gcd (n , k 1 , k 2) identical graphs, which belong to one of the three types of graphs: (i) C (Z n { 1 , k }) ; (i i) the Cartesian graph bundle C s □ φ C t over cycles; (i i i) the Cartesian product of the complete graph K 2 and a cycle. Naturally, to study the dispersability of C (Z n , { k 1 , k 2 }) can be reduced to study that of the above three types. Next, we solve the dispersability of the circulant graph C (Z n , { 1 , k }). Specifically, C (Z n , { 1 , k }) is dispersable if it is a bipartite; otherwise, it is nearly dispersable. In addition, we prove that bipartite circulant graphs are dispersable. [ABSTRACT FROM AUTHOR]

The bipartite toughness t B (G) of a non-complete bipartite graph G = (X , Y) is defined as t B (G) = min { | S | c (G − S) } , in which the minimum is taken over all proper subsets S ⊂ X (or S ⊂ Y) such that G − S is disconnected and c (G − S) > 1. A non-complete bipartite graph G is t B - tough if | S | ≥ t B c (G − S) for every proper subset S ⊂ X (or S ⊂ Y) with c (G − S) > 1. By incorporating the toughness and spectral conditions, we provide spectral radius and edge conditions for 2-factors in 1-tough balanced bipartite graphs. [ABSTRACT FROM AUTHOR]

The general position problem in graph theory asks for the largest set S of vertices of a graph G such that no shortest path of G contains more than two vertices of S. In this paper we consider a variant of the general position problem called the monophonic position problem , obtained by replacing 'shortest path' by 'induced path'. We prove some basic properties and bounds for the monophonic position number of a graph and determine the monophonic position number of some graph families, including unicyclic graphs, complements of bipartite graphs and split graphs. We show that the monophonic position number of triangle-free graphs is bounded above by the independence number. We present realisation results for the general position number, monophonic position number and monophonic hull number. Finally we discuss the complexity of the monophonic position problem. [ABSTRACT FROM AUTHOR]

A Roman { 3 } -dominating function on a graph G is a function f : V (G) → { 0 , 1 , 2 , 3 } having the property that for any vertex u ∈ V (G) , if f (u) = 0 , then ∑ v ∈ N G (u) f (v) ≥ 3 , and if f (u) = 1 , then ∑ v ∈ N G (u) f (v) ≥ 2. The weight of a Roman { 3 } -dominating function f is the sum f (V (G)) = ∑ v ∈ V (G) f (v) and the minimum weight of a Roman { 3 } -dominating function on G is called the Roman { 3 } -domination number of G and is denoted by γ { R 3 } (G). Given a graph G , Roman { 3 } - domination asks to find the minimum weight of a Roman { 3 } -dominating function on G. In this paper, we study the algorithmic aspects of Roman { 3 } - domination on various graph classes. We show that the decision version of Roman { 3 } - domination remains NP -complete for chordal bipartite graphs, planar graphs, star-convex bipartite graphs, and chordal graphs. We show that Roman { 3 } - domination cannot be approximated within a ratio of (1 3 − ɛ) ln | V (G) | for any ɛ > 0 unless P = NP for bipartite graphs as well as chordal graphs, whereas Roman { 3 } - domination can be approximated within a factor of O (ln Δ) for graphs having maximum degree Δ. We also show that Roman { 3 } - domination is APX -complete for graphs with maximum degree 4. On the positive side, we show that Roman { 3 } - domination can be solved in linear time for chain graphs and cographs. [ABSTRACT FROM AUTHOR]

We introduce the multicolored graph realization problem (MGR). The input to this problem is a colored graph (G , φ) , i.e., a graph G together with a coloring φ on its vertices. We associate each colored graph (G , φ) with a cluster graph (G φ) in which, after collapsing all vertices with the same color to a node, we remove multiple edges and self-loops. A set of vertices S is multicolored when S has exactly one vertex from each color class. The MGR problem is to decide whether there is a multicolored set S so that, after identifying each vertex in S with its color class, G [ S ] coincides with G φ. The MGR problem is related to the well-known class of generalized network problems, most of which are NP-hard, like the generalized Minimum Spanning Tree problem. The MGR is a generalization of the multicolored clique problem, which is known to be W [ 1 ] -hard when parameterized by the number of colors. Thus, MGR remains W [ 1 ] -hard, when parameterized by the size of the cluster graph. These results imply that the MGR problem is W [ 1 ] -hard when parameterized by any graph parameter on G φ , among which lies treewidth. Consequently, we look at the instances of the problem in which both the number of color classes and the treewidth of G φ are unbounded. We consider three natural such graph classes: chordal graphs, convex bipartite graphs and 2-dimensional grid graphs. We show that MGR is NP-complete when G φ is either chordal, biconvex bipartite, complete bipartite or a 2-dimensional grid. Our reductions show that the problem remains hard even when the maximum number of vertices in a color class is 3. In the case of the grid, the hardness holds even for graphs with bounded degree. We provide a complexity dichotomy with respect to cluster size. [ABSTRACT FROM AUTHOR]

If G = (V , E) is a (finite and simple) graph, we call an independent set X a gated independent set in G if for each x ∈ X , there exists a neighbor y of x such that (X ∖ { x }) ∪ { y } is an independent set in G. We define the gated independence number gi (G) of G to be the maximum cardinality of a gated independent set in G. We demonstrate that the gated independence number is closely related to both matching and domination parameters of graphs. We prove that the inequalities im (G) ⩽ gi (G) ⩽ m ur (G) hold for every graph G , where im (G) and m ur (G) denote the induced and uniquely restricted matching numbers of G. On the other hand, we show that γ i (G) ⩽ gi (G) and γ pr (G) ⩽ 2 gi (G) for every graph G without any isolated vertex, where γ i (G) and γ pr (G) denote the independence and paired domination numbers. Furthermore, we provide bounds on the gated independence number involving the order, size and maximum degree. In particular, we prove that gi (G) ⩾ n 5 for every n -vertex subcubic graph G without any isolated vertex or any component isomorphic to K 3 , 3 , and gi (B) ⩽ 3 n 8 for every n -vertex connected cubic bipartite graph B. [ABSTRACT FROM AUTHOR]

A graph G with four or more vertices is called bicritical if the removal of any pair of distinct vertices of G results in a graph with a perfect matching. A bicritical graph is minimal if the deletion of each edge results in a non-bicritical graph. Recently, Y. Zhang et al. and F. Lin et al. respectively showed that bicritical graphs without removable edges and minimal bricks have at least four cubic vertices. In this note, we show that minimal bicritical graphs also have at least four cubic vertices, so confirming O. Favaron and M. Shi's conjecture in the case of k = 2 on minimal k -factor-critical graphs. [ABSTRACT FROM AUTHOR]

A connected graph G is H - removable if H is a subgraph of G , G has at least | V (H) | + 2 vertices and G − V (H ′) has a perfect matching for every subgraph H ′ of G isomorphic to H. So a connected graph is k K 2 -removable if and only if it is k -extendable, where k K 2 is a matching of size k. Further G is an H - forced graph if G − V (H ′) has a unique perfect matching for every subgraph H ′ of G isomorphic to H. In this paper, we first characterize k K 2 -forced graphs for k ≥ 2 as K 2 k + 2 and K k + 1 , k + 1 by using randomly matchable graphs. Let P i denote a path with i vertices. We show that P 3 - and P 4 -removable graphs are factor-critical and 1-extendable respectively. By using ear decomposition, we obtain that a connected graph G is P 3 -forced if and only if G is K 5 or C 2 k + 1 (k ≥ 2). Finally we prove that a connected graph G is P 4 -forced if and only if G is isomorphic to K 6 , K 3 , 3 , C 2 k (k ≥ 3), the Petersen graph, a uniform theta graph Θ 3 n (n ≥ 3) or C 12 +. [ABSTRACT FROM AUTHOR]

A matching in a graph is a set of pairwise nonadjacent edges. A maximum matching is a matching which covers as many vertices as possible. In this paper, using the Gallai–Edmonds Structure Theorem, we obtain a characterization of graphs each of whose edges belongs to at most one maximum matching. [ABSTRACT FROM AUTHOR]

A connected nontrivial graph G is matching covered , if every edge of G is contained in a perfect matching of G. An edge e of a matching covered graph G is removable if G − e is still matching covered. Lovász and Plummer introduced removable edges in connection with ear decompositions of matching covered graphs. By characterizing the structure of removable edges, we obtain that the number of removable edges of Halin graphs G with even number of vertices, other than K 4 , C 6 ¯ and R 8 , is at least 1 4 (| V (G) | + 2) , and the lower bound is attainable. [ABSTRACT FROM AUTHOR]

The dichromatic number of a digraph G is the smallest integer χ a (G) such that the vertex set of G can be partitioned into χ a (G) sets, each of which induces an acyclic subdigraph. This is a generalization of the classic chromatic number of graphs. Here, we investigate the dichromatic number of the cartesian, direct, strong, and lexicographic products, generalizing some classic results on the chromatic number of products. More specifically, by letting □ denote the cartesian product, × the direct product, ⊠ the strong product, and G [ H ] the lexicographic product of G by H , we proved that the following inequalities, known to hold for the chromatic number of graphs, still hold for the dichromatic number of digraphs: χ a (G □ H) = max { χ a (G) , χ a (H) } ; χ a (G × H) ≤ min { χ a (G) , χ a (H) } ; and χ a (G [ H ]) = χ a (G [ K ↔ k ]) , where k = χ a (H) and K ↔ k denotes the complete digraph on k vertices. In addition, we investigate the products of directed cycles, giving exact values for χ a ( C → n × C → m) and χ a ( C → n ⊠ C → m) for every n , m , and for χ a ( C → n [ H ]) for every positive integer n. We also close the gap about the chromatic number of the strong product of a cycle by a bipartite graph, providing exact values for χ (C n ⊠ H) when H is bipartite. [ABSTRACT FROM AUTHOR]

A Roman dominating function (RDF) on a graph G is a function f : V (G) → { 0 , 1 , 2 } such that every vertex u ∈ V (G) with f (u) = 0 is adjacent to at least one vertex v ∈ V (G) with f (v) = 2. An independent Roman dominating function (IRDF) f on a graph G is a Roman dominating function such that the set of vertices u ∈ V (G) with f (u) ∈ { 1 , 2 } form an independent set on G. The weight of f is f (V (G)) = ∑ v ∈ V (G) f (v). The minimum weight of an RDF (IRDF) on G is the Roman domination number (independent Roman domination number) of G , denoted by γ R (G) ( i R (G)). The (independent) Roman domination problem asks for an (independent) Roman dominating function with minimum weight. In this work, we prove that the decision version of the (independent) Roman domination problem is NP -complete even when restricted to planar bipartite graphs with maximum degree three. Moreover, we study the (independent) Roman domination number on three infinite families of snarks. More specifically, we determine the (independent) Roman domination number for generalized Blanuša snarks and we present lower and upper bounds for the (independent) Roman domination number of Goldberg snarks and Loupekine Snarks. [ABSTRACT FROM AUTHOR]

Let L be list assignment of colors available for vertices of a graph G. An (L , r) -coloring of G is a proper coloring c such that for any vertex v ∈ V (G) , we have c (v) ∈ L (v) and ∣ c (N G (v)) ∣ ≥ min { d G (v) , r }. The list r -hued chromatic number of G , denoted as χ L , r (G) , is the least integer k , such that for list assignment L satisfying ∣ L (v) ∣ = k , for any v ∈ V (G) , G has an (L , r) -coloring. Let K m , n denote a complete bipartite graph. In [Discrete Math. 306(16)(2006) 1997–2004], it has been proved if n ≥ m ≥ 2 , then χ r (K m , n) =min { 2 r , n + m , r + m }. In this paper, we determine the list r -hued chromatic number of K m , n. [ABSTRACT FROM AUTHOR]

For a fixed property (graph class) Π , given a graph G and an integer k , the Π - deletion problem consists in deciding if we can turn G into a graph with the property Π by deleting at most k edges. The Π -deletion problem is known to be NP-hard for most of the well-studied graph classes, such as chordal, interval, bipartite, planar, comparability and permutation graphs, among others; even deletion to cacti is known to be NP-hard for general graphs. However, there is a notable exception: the deletion problem to trees is polynomial. Motivated by this fact, we study the deletion problem for some classes similar to trees, addressing in this way a knowledge gap in the literature. We prove that deletion to cacti is hard even when the input is a bipartite graph. On the positive side, we show that the problem becomes tractable when the input is chordal, and for the special case of quasi-threshold graphs we give a simpler and faster algorithm. In addition, we present sufficient structural conditions on the graph class Π that imply the NP-hardness of the Π -deletion problem, and show that deletion from general graphs to some well-known subclasses of forests is NP-hard. [ABSTRACT FROM AUTHOR]

We study the Maker–Maker version of the domination game introduced in 2018 by Duchêne et al. Given a graph, two players alternately claim vertices. The first player to claim a dominating set of the graph wins. As the Maker–Breaker version, this game is PSPACE -complete on split and bipartite graphs. Our main result is a linear time algorithm to solve this game in forests. We also give a characterization of the cycles where the first player has a winning strategy. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with the adjacency matrix A (G) , and let τ (G) denote the smallest positive eigenvalue of A (G). Let G n be the class of all connected bipartite graphs on n = 2 k vertices with a unique perfect matching. In this article, we characterize the graphs G in G n such that τ (G) does not exceed 1 2. Using the above characterization, we obtain the unique graphs in G n with the maximum and the second maximum τ , respectively. Further, we prove that the largest and the second largest limit points of the smallest positive eigenvalues of bipartite graphs with a unique perfect matching are 1 2 and the reciprocal of α 3 1 2 + α 3 − 1 2 , respectively, where α 3 is the largest root of x 3 − x − 1. [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. Let C 2 n be a cycle of length 2 n and let k = 2 , 3. It is shown for any ϵ > 0 , there exists T = T (ϵ) > 0 such that if n p > T , then Pr [ G (K 2 ((k + ϵ) n) , p) ⟶ k C 2 n ] → 1 as n → ∞ , for which the proof relies heavily on the sparse regularity lemma for multipartite graphs. [ABSTRACT FROM AUTHOR]

A graph G is said to be k -extendable if every matching of size k in G can be extended to a perfect matching of G , where k is a positive integer. We say G is 1-excludable if for every edge e of G , there exists a perfect matching excluding e. In this paper, we first establish a lower bound on the size (resp. the spectral radius) of G to guarantee that G is k -extendable. Then we determine a lower bound on the size (resp. the spectral radius) of G to guarantee that G is 1-excludable. All the corresponding extremal graphs are characterized. [ABSTRACT FROM AUTHOR]

Motivated by bipartite Gallai–Ramsey type problems, we consider edge-colorings of complete bipartite graphs without rainbow tree and matching. Given two graphs G and H , and a positive integer k , define the bipartite Gallai–Ramsey number bgr k (G : H) as the minimum number of vertices n such that n 2 ≥ k and for every N ≥ n , any coloring (using all k colors) of the complete bipartite graph K N , N contains a rainbow copy of G or a monochromatic copy of H. In this paper, we first describe the structures of a complete bipartite graph K n , n without rainbow P 4 + and 3 K 2 , respectively, where P 4 + is the graph consisting of a P 4 with one extra edge incident with an interior vertex. Furthermore, we determine the exact values or upper and lower bounds on bgr k (G : H) when G is a 3-matching or a 4-path or P 4 + , and H is a bipartite graph. [ABSTRACT FROM AUTHOR]

Paintability of graphs, which is also called online choosability of graphs, was introduced by Schauz and by Zhu in 2009, and has been studied in point of the difference from choosability of graphs. Compared with the choice number and the chromatic number, it is much more difficult to determine the paint number of a given graph. For example, even the 3-paintable complete bipartite graphs have not been characterized yet. In this paper, we focus on the paintability of complete bipartite graphs, especially m -paintability of K m + 1 , r. Let r OL (m) denote the least integer r such that K m + 1 , r is not m -paintable. In this paper, we determine the order of r OL (m) as r OL (m) = Θ (m m − 1). Let r (m) denote the least r such that K m + 1 , r is not m -choosable, for which Hoffman and Johnson Jr. determined as r (m) = m m − (m − 1) m = Θ (m m). As a corollary, we can show that r OL (m) / r (m) tends to 0 when m goes to infinity. [ABSTRACT FROM AUTHOR]

The slow coloring game was introduced by Mahoney, Puleo, and West and it is played by two players, Lister and Painter, on a graph G. In round i , Lister marks a nonempty subset M of V (G). By doing this he scores | M | points. Painter responds by deleting a maximal independent subset of M. This process continues until all vertices are deleted. Lister aims to maximize the score, while Painter aims to minimize it. The best score that both players can guarantee is called the slow coloring number or sum-color cost of G , denoted s ̊ (G). Puleo and West found that for an n -vertex tree T , the slow coloring number is at most ⌊ 3 n 2 ⌋ , and that the maximum can be reached when T contains a spanning forest with vertices of degree 1 or 3. This implies that every n-vertex graph G having a perfect matching satisfies s ̊ (G) ≥ ⌊ 3 n 2 ⌋. In this paper, we prove that for 3 k -connected graphs with | V (G) | ≥ 4 k and with a perfect matching the lower bound is higher: s ̊ (G) ≥ 3 n 2 + k. [ABSTRACT FROM AUTHOR]

A subgraph of an edge-colored graph is rainbow if all of its edges have different colors. Given a graph family G and a graph H , the anti-Ramsey number A R (G , H) is the maximum number of colors in an edge-coloring of a graph G ∈ G which has no rainbow copy of H. When G = { G } , we write A R (G , H) for short. Erdős, Simonovits and Sós introduced these numbers in the 1970s, they studied the case when G is a complete graph. Since then, many results have appeared considering G and H belonging to specific graph classes. In particular, Jendrol', Schiermeyer and Tu (Jendrol' et al., 2014) obtained an upper bound for A R (T n , k K 2) in terms of n and k for k ≥ 3 and n ≥ 2 k , where T n is the family of maximal planar graphs on n vertices. Jin and Ye (Jin and Ye, 2018) continued the study of anti-Ramsey numbers of matchings in planar graphs, by deriving an upper bound for A R (M n , k K 2) , where M n is the family of maximal outerplanar graphs on n vertices. In both works, examples are shown for which there are colorings using many colors while avoiding rainbow matchings, but the numbers of colors in these examples do not reach the upper bounds. The bounds of A R (T n , k K 2) were improved in following works by other researchers. This paper goes in the same direction of these two works, proving exact value for A R (B n , k K 2) in terms of n and k for n ≥ 6 and k ≥ 3 , where B n is the family of maximal bipartite outerplanar graphs on n vertices which contains a Hamilton cycle. [ABSTRACT FROM AUTHOR]

For k ∈ N , a k -acyclic colouring of a graph G is a function f : V (G) → { 0 , 1 , ... , k − 1 } such that (i) f (u) ≠ f (v) for every edge u v of G , and (ii) there is no cycle in G bicoloured by f. For k ∈ N , the problem k - Acyclic Colourability takes a graph G as input and asks whether G admits a k -acyclic colouring. Ochem (EuroComb 2005) proved that 3- Acyclic Colourability is NP-complete for bipartite graphs of maximum degree 4. Mondal et al. (2013) proved that 4- Acyclic Colourability is NP-complete for graphs of maximum degree five. We prove that for k ≥ 3 , k - Acyclic Colourability is NP-complete for bipartite graphs of maximum degree k + 1 , thereby generalising the NP-completeness result of Ochem, and adding bipartiteness to the NP-completeness result of Mondal et al.. In contrast, k - Acyclic Colourability is polynomial-time solvable for graphs of maximum degree at most 0. 38 k 3 / 4 . Hence, for k ≥ 3 , the least integer d such that k - Acyclic Colourability in graphs of maximum degree d is NP-complete, denoted by L a (k) , satisfies 0. 38 k 3 / 4 < L a (k) ≤ k + 1. We prove that for k ≥ 4 , k - Acyclic Colourability in d -regular graphs is NP-complete if and only if L a (k) ≤ d ≤ 2 k − 3. We also show that it is coNP-hard to check whether an input graph G admits a unique k -acyclic colouring up to colour swaps (resp. up to colour swaps and automorphisms). [ABSTRACT FROM AUTHOR]