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]

A new kind of bipartite graph is defined in this paper. The work is motivated mainly from a graph introduced by Al-Kaseasbeh and Erfanian [A bipartite graph associated to elements and cosets of subgroups of a finite group, AIMS Math. 6(10) (2021) 10395–10404] and partially from the undirected power graph of a group and from the inclusion graph. For a nontrivial group G, we define a simple undirected bipartite graph Γ(G) with the vertex set V (Γ(G)) = A ∪ B, where A is the set of all elements of the group G and B is the set of all subgroups H of G such that H≠{e} and two vertices a ∈ A and H ∈ B are adjacent if and only if a2 ∈ H. Here, we classify all the finite groups G whose bipartite graphs Γ(G) are planar. In addition, we also classify the finite groups G such that Γ(G) is outerplanar, maximal planar, maximal outerplanar, star, tree, claw graph, respectively. The planarity of the graph Γ(G) corresponding to an infinite group G has also been investigated here. It is also observed that Γ(G) satisfies Vizing’s conjecture. [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]

For a graph G , let i k (G) be the number of independent sets of size k in G. The independence polynomial I (G ; x) = ∑ k ≥ 0 i k (G) x k has been the focus of considerable research. In this paper, using the coefficients of independence polynomials, we order graphs with some given parameters. We first determine the extremal graph whose all coefficients of I (G ; x) are the largest (respectively, smallest) among all connected graphs (respectively, bipartite graphs) with given vertex cover number. Then we also derive the extremal graph whose all coefficients of I (G ; x) are the largest among all connected graphs (respectively, bipartite graphs) with given vertex dominate number. [ABSTRACT FROM AUTHOR]

Nakajima's graded quiver varieties naturally appear in the study of bases of cluster algebras. One particular family of these varieties, namely the bipartite determinantal varieties, can be defined for any bipartite quiver and gives a vast generalization of classical determinantal varieties with broad applications to algebra, geometry, combinatorics, and statistics. The ideals that define bipartite determinantal varieties are called bipartite determinantal ideals. We provide an elementary method of proof showing that the natural generators of a bipartite determinantal ideal form a Gröbner basis, using an S-polynomial construction method that relies on the Leibniz formula for determinants. This method is developed from an idea by Narasimhan and Caniglia–Guccione–Guccione. As applications, we study the connection between double determinantal ideals (which are bipartite determinantal ideals of a quiver with two vertices) and tensors, and provide an interpretation of these ideals within the context of algebraic statistics. [ABSTRACT FROM AUTHOR]

Aiming at problems such as the "straggler effect" caused by resource heterogeneity in federated learning in edge computing environments, this paper proposed a match-based model offloading for edge federated learning (Fed-MBMO). This method collected performance analysis results of edge devices, divided devices into strong and weak clients, and considered the time proportion of the four phases of model training, weak clients saved the time of backpropagation on the feature layers by freezing part of the model, and offload the model to the strong client for additional training, finally, the strong clients' feature layers were then reconstructed with the weak clients' fully connected layers. In order to improve the efficiency of model off- loading, the offloading cost matrix is constructed by comprehensively considering the similarity of model feature layers and task completion time, and transform the problem into an iterative solution of the optimal matching problem based on bipartite graph, the proposed approach used a KM-based model offloading algorithm and further analyzed the time complexity of the Fed-MBMO algorithm. Experimental results show that in the case of extremely heterogeneous resources and datasets, this method can accelerate model convergence, and the model training time can be reduced by an average of 46. 65 percent, 12. 66 percent and 38.07 percent compared to FedAvg, FedUE and Aergia, respectively. The experimental results show that the Fed-MBMO algorithm can effectively solve the "straggler effect "problem and significantly improve the efficiency of federated learning. [ABSTRACT FROM AUTHOR]

We prove that in a connected graph, the distances between non-cut vertices are odd if and only if it is the line graph of a strong unique independence tree. We then show that any such tree can be inductively constructed from stars using a simple operation. Further, we study the connected graphs in which the distances between non-cut vertices are even (shortly, NCE-graphs). Our main results on NCE-graphs are the following: we give a criterion of NCE-graphs, show that any bipartite graph is an induced subgraph of an NCE-graph, characterize NCE-graphs with exactly two leaves, characterize graphs that can be subdivided to NCE-graphs, and provide a characterization for NCE-graphs which are maximal with respect to the edge addition operation. [ABSTRACT FROM AUTHOR]

In this paper, we first give some sufficient criteria for normality of monomial ideals. As applications, we show that closed neighborhood ideals of complete bipartite graphs are normal, and hence satisfy the (strong) persistence property. We also prove that dominating ideals of complete bipartite graphs are nearly normally torsion-free. In addition, we show that dominating ideals of h -wheel graphs, under certain condition, are normal. [ABSTRACT FROM AUTHOR]

For a given graph H , its subdivisions carry the same topological structure. The existence of H -subdivisions within a graph G has deep connections with topological, structural and extremal properties of G. One prominent example of such a connection, due to Bollobás and Thomason and independently Komlós and Szemerédi, asserts that the average degree of G being d ensures a K Ω (d) -subdivision in G. Although this square-root bound is best possible, various results showed that much larger clique subdivisions can be found in a graph for many natural classes. We investigate the connection between crux, a notion capturing the essential order of a graph, and the existence of large clique subdivisions. This reveals the unifying cause underpinning all those improvements for various classes of graphs studied. Roughly speaking, when embedding subdivisions, natural space constraints arise; and such space constraints can be measured via crux. Our main result gives an asymptotically optimal bound on the size of a largest clique subdivision in a generic graph G , which is determined by both its average degree and its crux size. As corollaries, we obtain • a characterization of extremal graphs for which the square-root bound above is tight: they are essentially disjoint unions of graphs having crux size linear in d ; • a unifying approach to find a clique subdivision of almost optimal size in graphs which do not contain a fixed bipartite graph as a subgraph; • and that the clique subdivision size in random graphs G (n , p) witnesses a dichotomy: when p = ω (n − 1 / 2) , the barrier is the space, while when p = o (n − 1 / 2) , the bottleneck is the density. [ABSTRACT FROM AUTHOR]

An edge e of a matching covered graph G is removable if G−e is also matching covered. The notion of removable edge arises in connection with ear decompositions of matching covered graphs introduced by Lovász and Plummer. A nonbipartite matching covered graph G is a brick if it is free of nontrivial tight cuts. Carvalho, Lucchesi and Murty proved that every brick other than K4 and C6¯ has at least Δ−2 removable edges. A brick G is near‐bipartite if it has a pair of edges {e1,e2} such that G−{e1,e2} is a bipartite matching covered graph. In this paper, we show that in a near‐bipartite brick G with at least six vertices, every vertex of G, except at most six vertices of degree three contained in two disjoint triangles, is incident with at most two nonremovable edges; consequently, G has at least |V(G)|−62 removable edges. Moreover, all graphs attaining this lower bound are characterized. [ABSTRACT FROM AUTHOR]

For f:R2→R, let ΓR(f) be a two‐dimensional algebraically defined graph, that is, a bipartite graph where each partite set is a copy of R2 and two vertices (a,a2) and [x,x2] are adjacent if and only if a2+x2=f(a,x). It is known that ΓR(XY) has girth 6 and can be extended to the point‐line incidence graph of the classical real projective plane. However, it was unknown whether there exists f∈R[X,Y] such that ΓR(f) has girth 6 and is nonisomorphic to ΓR(XY). This paper answers this question affirmatively and thus provides a construction of a nonclassical real projective plane. This paper also studies the diameter and girth of ΓR(f) for families of bivariate functions f. [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]

Traditional community detection methods often rely solely on network topology, potentially overlooking the influence of attributes. However, community detection in attributed networks presents a unique challenge due to the complex interplay between network topology and node attributes. In this paper, we present AERW, a novel approach that integrates both network topology and node attributes for effective community detection. AERW leverages the principle of homophily by aggregating neighbor attributes within triangles to capture higher-order structural information. Then constructing a bipartite graph to effectively integrate topological and attribute information, ensuring that both aspects are equally represented in the community detection process. Next AERW utilizes hierarchical clustering applied to the probability transition matrix derived from the random walk, enabling the identification of community structures without needing prior knowledge of the number of communities. Extensive experimentation across synthetic and real-world networks underscores AERW's efficacy, establishing it as a superior approach in community detection within attributed networks. [ABSTRACT FROM AUTHOR]

In order to alleviate the issue of data sparsity, knowledge graphs are introduced into recommender systems because they contain diverse information about items. The existing knowledge graph enhanced recommender systems utilize both user–item interaction data and knowledge graph, but those methods ignore the semantic difference between interaction data and knowledge graph. On the other hand, for the item representations obtained from two kinds of graph structure data respectively, the existing methods of fusing representations only consider the item representations themselves, without considering the personalized preference of users. In order to overcome the limitations mentioned above, we present a recommendation method named Interaction-Knowledge Semantic Alignment for Recommendation (IKSAR). By introducing a semantic alignment module, the semantic difference between the interaction bipartite graph and the knowledge graph is reduced. The representation of user is integrated during the fusion of representations of item, which improves the quality of the fused representation of item. To validate the efficacy of the proposed approach, we perform comprehensive experiments on three datasets. The experimental results demonstrate that the IKSAR is superior to the existing methods, showcasing notable improvement. [ABSTRACT FROM AUTHOR]

Predicting postoperative prognosis is vital for clinical decision making in patients undergoing adrenalectomy (ADX). This study introduced GAPPA, a novel GNN-based approach, to predict post-ADX outcomes in patients with unilateral primary aldosteronism (UPA). The objective was to leverage the intricate dependencies between clinico-biochemical features and clinical outcomes using GNNs integrated into a bipartite graph structure to enhance prognostic prediction accuracy. We conceptualized prognostic prediction as a link prediction task on a bipartite graph, with nodes representing patients, clinico-biochemical features, and clinical outcomes, and edges denoting the connections between them. GAPPA utilizes GNNs to capture these dependencies and seamlessly integrates the outcome predictions into a graph structure. This approach was evaluated using a dataset of 640 patients with UPA who underwent unilateral ADX (uADX) between 1990 and 2022. We conducted a comparative analysis using repeated stratified five-fold cross-validation and paired t -tests to evaluate the performance of GAPPA against conventional machine learning methods and previous studies across various metrics. GAPPA significantly outperformed conventional machine learning methods and previous studies (p < 0.05) across various metrics. It achieved F1-score, accuracy, sensitivity, and specificity of 71.3 % ± 3.1 %, 71.1 % ± 3.4 %, 69.9 % ± 4.3 %, and 72.4 % ± 7.2 %, respectively, with an AUC of 0.775 ± 0.030. We also investigated the impact of different initialization schemes on GAPPA outcome-edge embeddings, highlighting their robustness and stability. GAPPA aids in preoperative prognosis assessment and facilitates patient counseling, contributing to prognostic prediction and advancing the applications of GNNs in the biomedical domain. [Display omitted] • We are the first to apply GNNs to improve prognostic prediction of UPA patients. • We introduce GAPPA for post-adrenalectomy prognostic outcome prediction. • GAPPA innovates by integrating outcome prediction into the graph structure. • GAPPA surpasses machine learning methods and prior research (p < 0.05). [ABSTRACT FROM AUTHOR]

Geography is a combinatorial game in which two players take turns moving a token along edges of a directed graph and deleting the vertex they came from. We expand upon work by Fox and Geissler, who classified the computational complexity of determining the winner of various Geography variants given a graph. In particular, we show NP-hardness for undirected partizan Geography with free deletion on bipartite graphs and directed partizan Geography with free deletion on acyclic graphs. In addition, we study Kotzig's Nim, a special case of Geography where the vertices are labeled and moves correspond to additions by fixed amounts. We partially resolve a conjecture by Tan and Ward about games with a certain move set. [ABSTRACT FROM AUTHOR]

Multi-view subspace clustering optimizes and integrates the graph structure information of each view. At present, the subspace clustering methods based on the abstract graph have better performance and improve the clustering results. Although the existing clustering algorithms have achieved excellent results, there are still four deficiencies: 1) Expensive time overhead, with most algorithms having a high time complexity; 2) Using fixed anchor points and the separation of anchor graph learning from subsequent graph construction, resulting in inadequate use of underlying graph structure between views; 3) Multi-view data have inevitable noise and in the original high-dimensional space data fusion may cause the loss of important information; 4) Most algorithms require additional post-processing to obtain clustering labels. To solve the above problems, we innovate a novel anchor-adaptive multi-view clustering algorithm based on a bipartite graph. Specifically, anchor graph learning and subspace graph construction are adaptively combined into a unified optimization framework. The projection matrix, consensus anchor matrix, and similarity matrix optimize each other to promote the clustering effect and structure a constrained bipartite graph to describe the relationship between representative points and sample points. At the same time, connectivity constraints are used to ensure that the connected components represent clusters directly. Our method has linear time complexity about sample size. Comparison experiments with the state-of-the-art algorithms demonstrate the effectiveness of the proposed method on various benchmark datasets. Moreover, our method is robust to noisy data and suitable for large-scale datasets. [ABSTRACT FROM AUTHOR]

Let Γ = (X , R) denote a finite, simple, connected, and undirected non-bipartite graph with vertex set X and edge set R. Fix a vertex x ∈ X , and define R f = R ∖ { y z | ∂ (x , y) = ∂ (x , z) } , where ∂ denotes the path-length distance in Γ. Observe that the graph Γ f = (X , R f) is bipartite. We say that Γ supports a uniform structure with respect to x whenever Γ f has a uniform structure with respect to x in the sense of Miklavič and Terwilliger [7]. Assume that Γ is a distance-regular graph with classical parameters (D , q , α , β) and diameter D ≥ 4. Recall that q is an integer such that q ∉ { − 1 , 0 }. The purpose of this paper is to study when Γ supports a uniform structure with respect to x. We studied the case q ≤ 1 in [3] , and so in this paper we assume q ≥ 2. Let T = T (x) denote the Terwilliger algebra of Γ with respect to x. Under an additional assumption that every irreducible T -module with endpoint 1 is thin, we show that if Γ supports a uniform structure with respect to x , then either α = 0 or α = q , β = q 2 (q D − 1) / (q − 1) , and D ≡ 0 (mod 6). [ABSTRACT FROM AUTHOR]

We correct an error in Theorem 13 in our published article Barik et al. [1]. [ABSTRACT FROM AUTHOR]

Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class C can be FO -transduced from a class of bounded-height trees (that is, has bounded shrubdepth) if, and only if, from C one cannot FO -transduce the class of all paths. This establishes one of the three remaining open questions posed by Blumensath and Courcelle about the MSO -transduction quasi-order, even in the stronger form that concerns FO -transductions instead of MSO -transductions. The backbone of our proof is a graph-theoretic statement that says the following: If a graph G excludes a path, the bipartite complement of a path, and a half-graph as semi-induced subgraphs, then the vertex set of G can be partitioned into a bounded number of parts so that every part induces a cograph of bounded height, and every pair of parts semi-induce a bi-cograph of bounded height. This statement may be of independent interest; for instance, it implies that the graphs in question form a class that is linearly χ -bounded. [ABSTRACT FROM AUTHOR]

Multi-view clustering is widely applied in engineering and scientific research. It helps reveal the underlying structures and correlations behind complex multi-view data. Graph-based multi-view clustering stands as a prominent research frontier within the multi-view clustering field, yet faces persistent challenges. Firstly, typically constructed initial input graphs for each view yields sparse clustering structure, hindering clustering performance. Secondly, as data sources proliferate, algorithms encounter escalating time complexities, notably in methods relying on n × n fully connected graphs. Thirdly, prevailing graph fusion strategies struggle to mitigate the impact of low-quality graphs, impeding overall efficacy. In this paper, we present a novel Multi-View Clustering method based on High-Order Bipartite Graph fusion (MCHBG). For the first two challenges, the introduced high-order bipartite graphs in MCHBG reveal richer clustering structures, effectively alleviating sparse clustering structure of the input graph, while keeping the overall algorithm's computational complexity controlled within O (n). For the third challenge, our graph fusion mechanism selectively integrates high-order bipartite graphs, and implicitly weights the selected bipartite graphs to mitigate the impact of low-quality bipartite graphs. MCHBG learns a structured fusion bipartite graph under the Laplacian rank constraint, which directly indicates the clusters of data. Extensive experimental results demonstrate the effectiveness and superiority of MCHBG. Code available: https://anonymous.4open.science/r/MCHBG. • Multi-view High-order Bipartite Graph Fusion for Enhanced Clustering. • Adaptive Fusion with Truncation Selection and Implicit Weighting • Computational Efficiency and Superiority in Multi-View Clustering. [ABSTRACT FROM AUTHOR]

Characterizing the graph having the maximum or minimum spectral radius in a given class of graphs is a classical problem in spectral extremal graph theory, originally proposed by Brualdi and Solheid. Given a graph G , a vertex subset S is called a maximum generalized 4-independent set of G if the induced subgraph G [ S ] dose not contain a 4-tree as its subgraph, and the subset S has maximum cardinality. The cardinality of a maximum generalized 4-independent set is called the generalized 4-independence number of G. In this paper, we firstly determine the connected graph (resp. bipartite graph, tree) having the largest spectral radius over all connected graphs (resp. bipartite graphs, trees) with fixed order and generalized 4-independence number, in addition, we establish a lower bound on the generalized 4-independence number of a tree with fixed order. Secondly, we describe the structure of all the n -vertex graphs having the minimum spectral radius with generalized 4-independence number ψ , where ψ ⩾ ⌈ 3 n / 4 ⌉. Finally, we identify all the connected n -vertex graphs with generalized 4-independence number ψ ∈ { 3 , ⌈ 3 n / 4 ⌉ , n − 1 , n − 2 } having the minimum spectral radius. • Characterize the extremal graphs having the maximum spectral radius in some given class of graphs. • Establish a sharp lower bound on the generalized 4-independence number of a tree with fixed order. • Describe the structure of connected graphs in terms of generalized 4-independence numbers and spectral radii. [ABSTRACT FROM AUTHOR]