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]

Statistical analysis of bipartite networks frequently requires randomly sampling from the set of all bipartite networks with the same degree sequence as an observed network. Trade algorithms offer an efficient way to generate samples of bipartite networks by incrementally 'trading' the positions of some of their edges. However, it is difficult to know how many such trades are required to ensure that the sample is random. I propose a stopping rule that focuses on the distance between sampled networks and the observed network, and stops performing trades when this distribution stabilizes. Analyses demonstrate that, for over 650 different degree sequences, using this stopping rule ensures a random sample with a high probability, and that it is practical for use in empirical applications. • Statistical analysis of bipartite networks requires randomly sampling. • It is difficult to determine whether a sample of bipartite networks is random. • The proposed stopping rule yields a random sample over 85% of the time. [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]

Zero forcing and maximum nullity are two important graph parameters which have been laboriously studied in order to aid in the resolution of the Inverse Eigenvalue problem. Motivated in part by an observation that the zero forcing number for the complement of a tree on n vertices is either n − 3 or n − 1 in one exceptional case, we consider the zero forcing number for the complement of more general graphs under certain conditions, particularly those that do not contain complete bipartite subgraphs. We also move well beyond trees and completely study all of the possible zero forcing numbers for the complements of unicyclic graphs and cactus graphs. Finally, we yield equality between the maximum nullity and zero forcing number of several families of graph complements considered. [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]

A graph G is k -factor-critical if G − S has a perfect matching for any subset S of V (G) with | S | = k. An integer k -matching of G is a function h : E (G) → { 0 , 1 , ... , k } satisfying ∑ e ∈ Γ (v) h (e) ≤ k for all v ∈ V (G) , where Γ (v) is the set of edges incident with v. An integer k -matching h of G is called perfect if ∑ e ∈ E (G) h (e) = k | V (G) | / 2. A graph G has the strong parity property if for every subset S of V (G) with even size, G has a spanning subgraph F with minimum degree at least one such that d F (v) ≡ 1 (mod 2) for all v ∈ S and d F (u) ≡ 0 (mod 2) for all u ∈ V (G) ﹨ S. In this paper, we provide edge number and spectral conditions for the k -factor-criticality, perfect integer k -matching and strong parity property of a graph, respectively. [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]

A complex unit gain graph, or T -gain graph, is a triple Φ = (G , T , φ) comprised of a simple graph G as the underlying graph of Φ, the set of unit complex numbers T = { z ∈ C : | z | = 1 } , and a gain function φ : E → → T with the property that φ (e i j) = φ (e j i) − 1. A cactus graph is a connected graph in which any two cycles have at most one vertex in common. In this paper, we firstly show that there does not exist a complex unit gain graph with nullity n (G) − 2 m (G) + 2 c (G) − 1 , where n (G) , m (G) and c (G) are the order, matching number, and cyclomatic number of G. Next, we provide a lower bound on the nullity for connected complex unit gain graphs and an upper bound on the nullity for complex unit gain bipartite graphs. Finally, we characterize all non-singular complex unit gain bipartite cactus graphs, which generalizes a result in Wong et al. (2022) [30]. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph and A (G) be the adjacency matrix of G. A diagonal matrix with diagonal entries ±1 is called a signature matrix. If A (G) is nonsingular and X = S A (G) − 1 S − 1 is entrywise nonnegative for some signature matrix S , then X can be viewed as the adjacency matrix of a unique weighted graph. It is called the inverse of G , denoted by G +. A graph G is said to have the reciprocal eigenvalue property (property(R)) if A (G) is nonsingular, and 1 λ is an eigenvalue of A (G) whenever λ is an eigenvalue of A (G). Further, if λ and 1 λ have the same multiplicity for each eigenvalue λ , then G is said to have the strong reciprocal eigenvalue property (property (SR)). It is known that for a tree T , the following conditions are equivalent: a) T + is isomorphic to T , b) T has property (R), c) T has property (SR) and d) T is a corona tree (it is a tree which is obtained from another tree by adding a new pendant at each vertex). Studies on the inverses, property (R) and property (SR) of bipartite graphs are available in the literature. However, their studies for the non-bipartite graphs are rarely done. In this article, we study the inverse and property (SR) for non-bipartite graphs. We first introduce an operation, which helps us to study the inverses of non-bipartite graphs. As a consequence, we supply a class of non-bipartite graphs for which the inverse graph G + exists and G + is isomorphic to G. It follows that each graph G in this class has property (SR). [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]

Let G be a graph and d i be the degree of a vertex v i in G. For a symmetric real function f (x , y) , one can get an edge-weighted graph in such a way that for each edge v i v j of G , the weight of v i v j is assigned by f (d i , d j). Hence, we have a weighted adjacency matrix A f (G) of G , in which the ij -entry is equal to f (d i , d j) if v i v j ∈ E (G) and 0 otherwise. In this paper, we use a unified approach to deal with the spectral properties of A f (G) for f (x , y) to be the functions of graphical or topological function-indices. Firstly, we obtain uniform interlacing inequalities for the weighted adjacency eigenvalues. For the edge-weight functions defined by almost a half of popularly used topological indices, it can be shown that our inequalities cannot be improved. Secondly, we establish a uniform equivalent condition for a connected graph G to have m distinct weighted adjacency eigenvalues. As an application, a combinatorial characterization for a graph to have two and three distinct weighted adjacency eigenvalues is presented, respectively. Moreover, bipartite graphs and unicyclic graphs with three distinct weighted adjacency eigenvalues are characterized. This paper attempts to unify the spectral study for weighted adjacency matrices of graphs with degree-based edge-weights. [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]

We investigate a graph-theoretic approach to the problem of distinguishing quantum product states in the fundamental quantum communication framework called local operations and classical communication (LOCC). We identify chordality as the key graph structure that drives distinguishability in one-way LOCC, and we derive a one-way LOCC characterization for chordal graphs that establishes a connection with the theory of matrix completions. We also derive minimality conditions on graph parameters that allow for the determination of indistinguishability of states. We present a number of applications and examples built on these results. [ABSTRACT FROM AUTHOR]

Let a = (a i) i ≥ 1 be a sequence in a field F , and f : F × F → F be a function such that f (a i , a i) ≠ 0 for all i ≥ 1. For any tournament T over [ n ] , consider the n × n symmetric matrix M T with zero diagonal whose (i , j) th entry (for i < j) is f (a i , a j) if i → j in T , and f (a j , a i) if j → i in T. It is known [3] that if T is a uniformly random tournament over [ n ] , then rank (M T) ≥ (1 2 − o (1)) n with high probability when char (F) ≠ 2 and f is a linear function. In this paper, we investigate the other extremal question: how low can the ranks of such matrices be? We work with sequences a that take only two distinct values, so the rank of any such n × n matrix is at least n / 2. First, we show that the rank of any such matrix depends on whether an associated bipartite graph has certain eigenvalues of high multiplicity. Using this, we show that if f is linear, then there are real matrices M T (f ; a) of rank at most n 2 + O (1). For rational matrices, we show that for each ε > 0 we can find a sequence a (ε) for which there are matrices M T (f ; a) of rank at most (1 2 + ε) n + O (1). These matrices are constructed from symmetric designs, and we also use them to produce bisection-closed families of size greater than ⌊ 3 n / 2 ⌋ − 2 for n ≤ 15 , which improves the previously best known bound given in [5]. [ABSTRACT FROM AUTHOR]

Bipartite networks serve as highly suitable models to represent systems involving interactions between two distinct types of entities, such as online dating platforms, job search services, or e-commerce websites. These models can be leveraged to tackle a number of tasks, including link prediction among the most useful ones, especially to design recommendation systems. However, if this task has garnered much interest when conducted on unipartite (i.e. standard) networks, it is far from being the case for bipartite ones. In this study, we address this gap by performing an experimental comparison of 19 link prediction methods able to handle bipartite graphs. Some come directly from the literature, and some are adapted by us from techniques originally designed for unipartite networks. We also propose to repurpose recommendation systems based on graph convolutional networks (GCN) as a novel link prediction solution for bipartite networks. To conduct our experiments, we constitute a benchmark of 3 real-world bipartite network datasets with various topologies. Our results indicate that GCN-based personalized recommendation systems, which have received significant attention in recent years, can produce successful results for link prediction in bipartite networks. Furthermore, purely heuristic metrics that do not rely on any learning process, like the Structural Perturbation Method (SPM), can also achieve success. [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]

The paper concentrates on the issue of distributed disturbance observer-based nonfragile bipartite consensus within nonlinear delayed multiagent systems, encompassing both leaderless and leader-following structures. The delays under consideration are nonuniform, manifesting in the state, the nonlinearity, and the communication processes. To suppress the external disturbances and the observer gain perturbations, distributed nonfragile disturbance observers pertaining to relative output and communication delays are developed to estimate the external disturbances for each agent. Employing the developed disturbance observer, distributed control protocols for nonfragile bipartite consensus are constructed incorporating states, estimated disturbances, and communication delays. These protocols can ensure bipartite consensus, compensate for external disturbances, and tolerate uncertainties in control gain. New augmented Lyapunov-Krasovskii functions are formulated by introducing the triple integral term and the augmented vector. The new bipartite consensus criteria for the studied multiagent systems are established with less conservatism by employing the techniques on second-order Bessel-Legendre integral inequality, reciprocally convex combination, and free weight matrix. Finally, numerical simulations and comparisons are performed for both leaderless and leader-following scenarios, thereby validating and enhancing the theoretical outcomes. • Multiagent systems with nonlinearity, disturbance and multiple delay, is considered. • Both cooperative and antagonistic relationships are all considered in consensus. • The perturbations in both observer and bipartite consensus protocol. • New Lyapunov-Krasovskii functions, and Bessel-Legendre inequality are employed. [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]

Let ρ (G) be the spectral radius of a graph G with m edges. Let S m − k + 1 k be the graph obtained from K 1 , m − k by adding k disjoint edges within its independent set. Nosal's theorem states that if ρ (G) > m , then G contains a triangle. Zhai and Shu showed that any non-bipartite graph G with m ≥ 26 and ρ (G) ≥ ρ (S m 1) > m − 1 contains a quadrilateral unless G ≅ S m 1 M.Q. Zhai and J.L. Shu (2022) [25]. Wang proved that if ρ (G) ≥ m − 1 for a graph G with size m ≥ 27 , then G contains a quadrilateral unless G is one out of four exceptional graphs Z.W. Wang (2022) [22]. In this paper, we show that any non-bipartite graph G with size m ≥ 51 and ρ (G) ≥ ρ (S m − 1 2) > m − 2 contains a quadrilateral unless G ≅ S m 1 or G ≅ S m − 1 2. Moreover, we show that if ρ (G) ≥ ρ (S m + 4 2 , 2 −) for a graph G with even size m ≥ 74 , then G contains a C 5 + unless G ≅ S m + 4 2 , 2 − , where C t + denotes the graph obtained from C t and C 3 by identifying an edge, S n , k denotes the graph obtained by joining every vertex of K k to n − k isolated vertices and S n , k − denotes the graph obtained from S n , k by deleting an edge incident to a vertex of degree k , respectively. [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]