Search

Investigation of chemical applicability and mathematical properties of topological indices is the contemporary research trend in chemical graph theory. The geometric arithmetic index (GA) stands out as an well nurtured index having strong correlation with properties and activities of molecules. Its exponential variant (EGA) is investigated here from chemical and mathematical point of view. The chemical connection of EGA is explored by assessing its structure–property modelling ability and isomer discrimination potential. Its mathematical features are demonstrated by finding bounds for numerous classes of graphs with characterizing extremal structures. Second maximum and minimum trees are characterized with respect to the EGA index. [ABSTRACT FROM AUTHOR]

Bipartite networks model relationships between two types of vertices and are prevalent in real-world applications. The departure of vertices in a bipartite network reduces the connections of other vertices, triggering their departures as well. This may lead to a breakdown of the bipartite network and undermine any downstream applications. Such cascading vertex departure can be captured by (α , β) -core, a cohesive subgraph model on bipartite networks that maintains the minimum engagement levels of vertices. Based on (α , β) -core, we aim to ensure the vertices are highly engaged with the bipartite network from two perspectives. (1) From a pre-emptive perspective, we study the anchored (α , β) -core problem, which aims to maximize the size of the (α , β) -core by including some "anchor" vertices. (2) From a defensive perspective, we study the collapsed (α , β) -core problem, which aims to identify the critical vertices whose departure can lead to the largest shrink of the (α , β) -core. We prove the NP-hardness of these problems and resort to heuristic algorithms that choose the best anchor/collapser iteratively under a filter-verification framework. Filter-stage optimizations are proposed to reduce "dominated" candidates and allow computation-sharing. In the verification stage, we select multiple candidates for improved efficiency. Extensive experiments on 18 real-world datasets and a billion-scale synthetic dataset validate the effectiveness and efficiency of our proposed techniques. [ABSTRACT FROM AUTHOR]

We develop a model of contests on networks. Each player is connected to a set of contests and exerts a single effort to increase the probability of winning each contest to which she is connected. We explore how behavior is shaped by the pattern of interactions and characterize the networks that tend to induce greater effort; in particular, we show that the complete bipartite network is the unique structure that maximizes aggregate player effort. We also obtain a new exclusion result—akin to the Exclusion Principle of Baye et al. (Am Econ Rev 83(1):289-294, 1993)—which holds under the lottery CSF, and contrasts prior work in contests. Finally, new insight into uniqueness of equilibrium for network contest games is provided. Our framework has a broad range of applications, including research and development, advertising, and research funding. [ABSTRACT FROM AUTHOR]

The essential source of errors in machining on five-axis milling centres are errors caused by the improper calibration of a machine tool, setup errors and a process plan which is not designed optimally. For the multilateral machining of the complex, precise parts of machines, a process plan should include, before and during the process, coordinate measurements by means of a touch probe in order to verify previously made surfaces or to determine accurately the position and orientation of a local coordinate system. The uncertainty of these measurements is connected with the estimate precision of performing the manufactured parts. This paper presents a tool devised for determining the uncertainty of the results of coordinate measurements by a simulation method, which is also useful at the stage of machine tool calibration. A basis of this method is a bipartite graph with a tree structure. Transitions in the graph constitute a set of elementary measurement activities and analytical activities which determine the uncertainty of the position and orientation of respective geometric features and abstract objects. Based on the results of the conducted simulation tests it is possible to build analytical models for the rapid determination of measurement uncertainty. The tool devised is aimed at vector dimensioning and therefore it enables simple extension, including integration with geometric dimensioning and tolerancing. This paper includes an example of applying the method devised, which confirms its practicability. [ABSTRACT FROM AUTHOR]

The timely and accurate prediction of maize (Zea mays L.) yields prior to harvest is critical for food security and agricultural policy development. Currently, many researchers are using machine learning and deep learning to predict maize yields in specific regions with high accuracy. However, existing methods typically have two limitations. One is that they ignore the extensive correlation in maize planting data, such as the association of maize yields between adjacent planting locations and the combined effect of meteorological features and maize traits on maize yields. The other issue is that the performance of existing models may suffer significantly when some data in maize planting records is missing, or the samples are unbalanced. Therefore, this paper proposes an end-to-end bipartite graph neural network-based model for trait data imputation and yield prediction. The maize planting data is initially converted to a bipartite graph data structure. Then, a yield prediction model based on a bipartite graph neural network is developed to impute missing trait data and predict maize yield. This model can mine correlations between different samples of data, correlations between different meteorological features and traits, and correlations between different traits. Finally, to address the issue of unbalanced sample size at each planting location, we propose a loss function based on the gradient balancing mechanism that effectively reduces the impact of data imbalance on the prediction model. When compared to other data imputation and prediction models, our method achieves the best yield prediction result even when missing data is not pre-processed. [ABSTRACT FROM AUTHOR]

Matrix factorization has demonstrated outstanding performance in machine learning. Recently, graph-based matrix factorization has gained widespread attention. However, graph-based methods are only suitable for handling small amounts of data. This paper proposes a fast semi-supervised learning method using only matrix factorization, which considers both global and local information. By introducing bipartite graphs into symmetric matrix factorization, the technique can handle large datasets effectively. It is worth noting that by utilizing tag information, the proposed symmetric matrix factorization becomes convex and unconstrained, i.e., the non-convex problem min x (1 − x 2) 2 is transformed into a convex problem. This allows it to be optimized quickly using state-of-the-art unconstrained optimization algorithms. The computational complexity of the proposed method is O (n m d) , which is much lower than that of the original symmetric matrix factorization, which is O (n 2 d) , and even lower than that of other anchor-based methods, which is O (n m d + m 2 n + m 3) , where n represents the number of samples, d represents the number of features, and m ≪ n represents the number of anchors. The experimental results on multiple public datasets indicate that the proposed method achieves higher performance in less time. [ABSTRACT FROM AUTHOR]

Recently, considerable attention has been directed toward graph-based semi-supervised learning (GSSL) as an effective approach for data labeling. Despite the progress achieved by current methodologies, several limitations persist. Firstly, many studies treat all samples equally in terms of weight and influence, disregarding the potential increased importance of samples near decision boundaries. Secondly, the detection of outlier-labeled data is crucial, as it can significantly impact model performance. Thirdly, existing models often struggle with predicting labels for unseen test data, restricting their utility in practical applications. Lastly, most graph-based algorithms rely on affinity matrices that capture pairwise similarities across all data points, thus limiting their scalability to large-scale databases. In this paper, we propose a novel GSSL algorithm tailored for large-scale databases, leveraging anchor points to mitigate the challenges posed by large affinity matrices. Additionally, our method enhances the influence of nodes near decision boundaries by assigning different weights based on their importance and using a mapping function from feature space to label space. Leveraging this mapping function enables direct label prediction for test samples without requiring iterative learning processes. Experimental evaluations on two extensive datasets (Norb and Covtype) demonstrate that our approach is scalable and outperforms existing GSSL methods in terms of performance metrics. [ABSTRACT FROM AUTHOR]

For a given graph G, the second Zagreb eccentricity index ξ 2 (G) is defined as the product of the eccentricities of two adjacent vertex pairs in G. This paper mainly studies the problem of determining the graphs that minimize the second Zagreb eccentricity index among n-vertex bipartite graphs with a fixed number of edges and diameter. To be specific, we determine the sharp lower bound on the second Zagreb eccentricity index over the bipartite graphs of order n in terms of fixed edges and diameter. The extremal graphs attaining these lower bounds are fully characterized. [ABSTRACT FROM AUTHOR]

In this paper we determine the pair difference cordial number of degree splitting graph of bistar, complete bipartite graph, ladder, wheel. [ABSTRACT FROM AUTHOR]

A linear forest is a graph consisting of paths. In this paper, the authors determine the maximum number of edges in an (m, n)-bipartite graph which does not contain a linear forest consisting of paths on at least four vertices for n ≥ m when m is sufficiently large. [ABSTRACT FROM AUTHOR]

Electroencephalogram (EEG) signals are derived from the central nervous system and inherently difficult to camouflage, leading to the recent popularity of EEG-based emotion recognition. However, due to the non-stationary nature of EEG, inter-subject variabilities become obstacles for recognition models to well adapt to different subjects. In this paper, we propose a novel approach called semi-supervised bipartite graph construction with active EEG sample selection (SBGASS) for cross-subject emotion recognition, which offers two significant advantages. Firstly, SBGASS adaptively learns a bipartite graph to characterize the underlying relationships between labeled and unlabeled EEG samples, effectively implementing the semantic connection for samples from different subjects. Secondly, we employ active sample selection technique in this paper to reduce the impact of negative samples (outliers or noise in the data) on bipartite graph construction. Drawing from the experimental results with the SEED-IV data set, we have gained the following three insights. (1) SBGASS actively rejects negative labeled samples, which helps mitigate the impact of negative samples when constructing the optimal bipartite graph and improves the model performance. (2) Through the learned optimal bipartite graph in SBGASS, the transferability of labeled EEG samples is quantitatively analyzed, which exhibits a decreasing tendency as the distance between each labeled sample and the corresponding class centroid increases. (3) Besides the improved recognition accuracy, the spatial-frequency patterns in emotion recognition are investigated by the acquired projection matrix. [ABSTRACT FROM AUTHOR]

In this paper we introduce and study a new graph-theoretic invariant called the bi-Wiener index. The bi-Wiener index W b (G) of a bipartite graph G is defined as the sum of all (shortest-path) distances between two vertices from different parts of the bipartition of the vertex set of G. We start with providing a motivation connected with the potential uses of the new invariant in the QSAR/QSPR studies. Then we study its behavior for trees. We prove that, among all trees of order n ≥ 4 , the minimum value of W b is attained for the star S n , and the maximum W b is attained at path P n for even n, or at path P n and B n (2) for odd n where B n (2) is a broom with maximum degree 3. We also determine the extremal values of the ratio W b (T n) / W (T n) over all trees of order n. At the end, we indicate some open problems and discuss some possible directions of further research. [ABSTRACT FROM AUTHOR]

For a subgraph G of a complete graph K n , the K n -complement of G, denoted by K n - G , is the graph obtained from K n - G by removing all the edges of G. In this paper, we express the number of spanning trees of the K n -complement K n - G of a bipartite graph G in terms of the determinant of the biadjcency matrices of all induced balanced bipartite subgraphs of G, which are nonsingular, and we derive formulas of the number of spanning trees of K n - G for various important classes of bipartite graphs G, some of which generalize some previous results. [ABSTRACT FROM AUTHOR]

Bipartite graphs are naturally used to model relationships between two types of entities, such as people-location, user-post, and investor-stock. When modeling real-world applications like disease outbreaks, edges are often enriched with temporal information, leading to temporal bipartite graphs. While reachability has been extensively studied on (temporal) unipartite graphs, it remains largely unexplored on temporal bipartite graphs. To fill this research gap, we study the reachability problem on temporal bipartite graphs in this paper. Specifically, a vertex u reaches a vertex w in a temporal bipartite graph G if u and w are connected through a series of consecutive wedges with time constraints. To efficiently answer if a vertex can reach the other vertex, we propose an index-based method by adapting the idea of 2-hop labeling. Effective optimization strategies and parallelization techniques are devised to accelerate the index construction process. To better support real-life scenarios, we further show how the index is leveraged to efficiently answer other types of queries, e.g., single-source reachability and earliest-arrival path queries. In addition, we propose an efficient method to handle incremental maintenance of the index structure. Extensive experiments on 16 real-world graphs demonstrate the effectiveness and efficiency of our proposed techniques. [ABSTRACT FROM AUTHOR]

The essential source of errors in machining on five-axis milling centres are errors caused by the improper calibration of a machine tool, setup errors and a process plan which is not designed optimally. For the multilateral machining of the complex, precise parts of machines, a process plan should include, before and during the process, coordinate measurements by means of a touch probe in order to verify previously made surfaces or to determine accurately the position and orientation of a local coordinate system. The uncertainty of these measurements is connected with the estimate precision of performing the manufactured parts. This paper presents a tool devised for determining the uncertainty of the results of coordinate measurements by a simulation method, which is also useful at the stage of machine tool calibration. A basis of this method is a bipartite graph with a tree structure. Transitions in the graph constitute a set of elementary measurement activities and analytical activities which determine the uncertainty of the position and orientation of respective geometric features and abstract objects. Based on the results of the conducted simulation tests it is possible to build analytical models for the rapid determination of measurement uncertainty. The tool devised is aimed at vector dimensioning and therefore it enables simple extension, including integration with geometric dimensioning and tolerancing. This paper includes an example of applying the method devised, which confirms its practicability.

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]

By a classical result of Brodmann, the function depthR/I^t is asymptotically a constant, i.e. there is a number s such that depthR/I^t = depthR/I^s for t > s. One calls the smallest number s with this property the index of depth stability of I and denotes it by dstab(I). This invariant remains mysterious till now. The main result of this paper gives an explicit formula for dstab(I) when I is an arbitrary ideal generated by squarefree monomials of degree 2. That is the first general case where one can characterize dstab(I) explicitly. The formula expresses dstab(I) in terms of the associated graph. The proof involves new techniques which relate different topics such as simplicial complexes, systems of linear inequalities, graph parallelizations, and ear decompositions. It provides an effective method for the study of powers of edge ideals. [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]

Copyright of Journal of Central China Normal University is the property of Huazhong Normal University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Fuzzy k-means clustering is widely acknowledged for its remarkable performance in data clustering. However, its effectiveness must improve when dealing with high-dimensional data characterized by complex distributions, leading to subpar clustering results. To tackle this challenge, we introduce a novel clustering method named Joint Learning of Fuzzy Embedded Clustering and Non-negative Spectral Clustering (FECNSC). Initially, FECNSC utilizes rapid spectral embedding to reduce the dimensionality of the data. Subsequently, it incorporates fuzzy clustering and non-negative spectral clustering in a unified framework. The novel fuzzy clustering method enhances fuzzy membership by regularising of non-negative spectral clustering. Our experimental results demonstrate the overall superiority of FECNSC in terms of accuracy, normalized mutual information, and purity across various benchmark datasets, surpassing multiple advanced methods. Therefore, FECNSC is an efficient solution for managing data with complex distributions. [ABSTRACT FROM AUTHOR]

Existing methods in article recommendation fail to fully use the article information, or pay less attention to the correlations among articles and "User-Article"s, resulting in inaccurate recommendation performance and weak personalized recommendation ability. Therefore, we design an article recommendation model based on Dual-AutoEncoder & Bipartite Graph (DAEBG): we build a Dual-AutoEncoder, consisting of an Attention-based AutoEncoder and a Graph AutoEncoder, for article basic features of "Title and Abstract" and the correlation features among articles by the "Tag and Citation" information, which are the input of DAEBG. Second, we design a correlation extraction network with Resource Allocation-based Bipartite Graph to extract the correlation feature embeddings of "User-Article"s. Finally, we employ the Probabilistic Matrix Factorization to fuse and update these feature embeddings, consider all kinds of features comprehensively, and avoid the sparse matrix and cold start problems. The output of DAEBG is a rating matrix, which is used for article recommendation. Experimental results show that DAEBG outperforms the other recommended methods in all experiments with different data characteristics (sparse or dense), which could help people choose the targets that better match their interests from a huge amount of articles. [ABSTRACT FROM AUTHOR]

Motivation The advent of multimodal omics data has provided an unprecedented opportunity to systematically investigate underlying biological mechanisms from distinct yet complementary angles. However, the joint analysis of multi-omics data remains challenging because it requires modeling interactions between multiple sets of high-throughput variables. Furthermore, these interaction patterns may vary across different clinical groups, reflecting disease-related biological processes. Results We propose a novel approach called Differential Canonical Correlation Analysis (dCCA) to capture differential covariation patterns between two multivariate vectors across clinical groups. Unlike classical Canonical Correlation Analysis, which maximizes the correlation between two multivariate vectors, dCCA aims to maximally recover differentially expressed multivariate-to-multivariate covariation patterns between groups. We have developed computational algorithms and a toolkit to sparsely select paired subsets of variables from two sets of multivariate variables while maximizing the differential covariation. Extensive simulation analyses demonstrate the superior performance of dCCA in selecting variables of interest and recovering differential correlations. We applied dCCA to the Pan-Kidney cohort from the Cancer Genome Atlas Program database and identified differentially expressed covariations between noncoding RNAs and gene expressions. Availability and Implementation The R package that implements dCCA is available at https://github.com/hwiyoungstat/dCCA. [ABSTRACT FROM AUTHOR]

The problem of recommender system is very popular with myriad available solutions. Recommender systems recommend items to users and help them in narrowing their search from huge amount of options available to the user. In this work, a novel approach for the recommendation problem is proposed by incorporating techniques from the link prediction problem in social networks. The proposed approach models the typical user-item information as a bipartite network, and predicts future links using link prediction measures, in which link prediction would actually mean recommending an item to a user. The standard recommender system methods suffer from the problems of sparsity and scalability. Since link prediction measures involve computations pertaining to local neighborhoods in the network, this approach would lead to a scalable solution to recommendation. In this work, we present top k links that are predicted by link prediction measures as recommendations to the users. Our work initially applies different existing link prediction measures to the recommendation problem by making suitable adaptations. The prime contribution of this work is to propose a recommendation framework routed from link prediction problem in social networks, that effectively utilizes probabilistic measures of link prediction and embed temporal data accessible on existing links. The proposed approach is evaluated on one movie-rating dataset of MovieLens, two product-rating datasets of Epinions & Amazon and one hotel-rating dataset of TripAdvisor. Results show that the link prediction measures based on temporal probabilistic information prove to be more effective in improving the quality of recommendation. Especially, Temporal cooccurrence probability measure improves the area under ROC curve (AUROC) by 10% for MovieLens, 23% for Epinions, 17% for TripAdvisor, 9% for Amazon over standard item-based collaborative filtering method. Similar improved performance is observed in terms of area under Precision-Recall curve (AUPR) as well as Normalized Rank-Score. [ABSTRACT FROM AUTHOR]

A given graph H is called realizable by a graph G if G [ N (v) ] ≅ H for every vertex v of G. The Trahtenbrot–Zykov problem says that which graphs are realizable. We consider a problem somewhat opposite in a more general setting. Let t be a positive integer. We characterize all graphs G such that G - N [ v ] ∈ F for every vertex v of G, where F is the set of all t-regular graphs. Indeed, for 1 ≤ t ≤ 3 , the graphs are characterized by the same authors recently. Let t ≥ 4 . In this paper, we prove that there is no graph G such that G - N [ u ] ∈ F for each vertex u ∈ V (G) if G - N [ v ] ≅ H ∈ F for some vertex v ∈ V (G) and d i a m (H) ≥ 4 . In addition, we characterize all graphs G such that G - N [ v ] ≅ H for each v ∈ V (G) if H is one of two special graphs whose diameter are 2 and 3, respectively. [ABSTRACT FROM AUTHOR]

Many real‐world applications can be modelled as graphs or networks, including social networks and biological networks. The theory of algebraic combinatorics provides tools to analyze the functioning of these networks, and it also contributes to the understanding of complex systems and their dynamics. Algebraic methods help uncover hidden patterns and properties that may not be immediately apparent in a visual representation of a graph. In this paper, we introduce left and right inverse graphs associated with finite loop structures and two mappings, P‐edge labeling and V‐edge labeling, of Latin squares. Moreover, this work includes some structural and graphical results of the commutator subloop, nucleus, and loop isotopes of inverse property quasigroups. [ABSTRACT FROM AUTHOR]

Plant–animal interactions constitute a recurrent and central focus in ecological research, with pollination representing one of its most extensively studied aspects. While certain insect orders have traditionally received considerable attention due to their abundance as flower visitors and their efficiency in pollination, it is undeniable that the significance of other less popular and neglected flower visitors cannot be overlooked. In this regard, velvet ants (Hymenoptera: Mutillidae and Myrmosidae) constitute an excellent study model, as the knowledge of their ecology (e.g., their feeding preferences) is still very limited despite being reported as common flower visitors. In this study, we conducted a comprehensive global review of velvet ant floral visitation patterns using citizen science data, literature records and unpublished data. We used network metrics to explore their flower‐visit preferences on a global scale, as well as depending on the bioregion where the interaction was recorded and the sex of the velvet ants. In addition, we explored their potential role as pollen vectors examining the number of photographic records where velvet ants had pollen attached to their bodies. Our analyses revealed that velvet ants are generalist flower visitors of a wide range of plant families, with Apiaceae, Asteraceae, Euphorbiaceae, Rhamnaceae and Fabaceae as the most visited. Despite differences in flowering plant and velvet ant composition across bioregions causing differences in plant‐velvet ant interactions, velvet ants visited flowering plants in a generalistic way across the globe. Males and females seemed to visit different plant communities, with males being more generalist than females. Furthermore, 42.7% (likely an underestimation) of the photographic records of velvet ants visiting flowers showed pollen attached to their bodies in the same way as in other pollinating insects, suggesting the same potential role as pollinators. There remains ample scope for ongoing investigation to comprehensively assess the importance of numerous arthropods, including velvet ants, not only as flower visitors but also as potential pollinators. [ABSTRACT FROM AUTHOR]

Bipartite graph representation learning aims to obtain node embeddings by compressing sparse vectorized representations of interactions between two types of nodes, e.g., users and items. Incorporating structural attributes among homogeneous nodes, such as user communities, improves the identification of similar interaction preferences, namely, user/item embeddings, for downstream tasks. However, existing methods often fail to proactively discover and fully utilize these latent structural attributes. Moreover, the manual collection and labeling of structural attributes is always costly. In this article, we propose a novel approach called Dirichlet Max-margin Matrix Factorization (DM3F), which adopts a self-supervised strategy to discover latent structural attributes and model discriminative node representations. Specifically, in self-supervised learning, our approach generates pseudo group labels (i.e., structural attributes) as a supervised signal using the Dirichlet process without relying on manual collection and labeling, and employs them in a max-margin classification. Additionally, we introduce a Variational Markov Chain Monte Carlo algorithm (Variational MCMC) to effectively update the parameters. The experimental results on six real datasets demonstrate that, in the majority of cases, the proposed method outperforms existing approaches based on matrix factorization and neural networks. Furthermore, the modularity analysis confirms the effectiveness of our model in capturing structural attributes to produce high-quality user embeddings. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Harbin University of Science & Technology is the property of Journal of Harbin University of Science & Technology and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

An independent set in a graph G is a set of pairwise nonadjacent vertices of G. The independence number, α , of G is the maximum cardinality of an independent set in G. An independent set in G is maximum if it has cardinality α . Mohr and Rautenbach determined the n-vertex trees (resp. connected graphs, disconnected graphs) with independence number α having the largest number of maximum independent sets. As a continuance of these works, we give complete characterizations among the following families of graphs: the n-vertex forests with independence number α having the first three largest number of maximum independent sets; the n-vertex trees with independence number α having the second and third largest number of maximum independent sets; the bipartite graphs (containing at least one cycle) of order n and independence number α having the maximum number of maximum independent sets; the disconnected n-vertex graphs with independence number α having the second largest number of maximum independent sets. Furthermore, we obtain a complete classification of connected graphs with order n and independence number n - 3 , which gives a solution to an open problem of Derikvand and Oboudi. [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]

Let G be a simple graph with the adjacency matrix $ A(G) $ A (G). Let $ \tau (G) $ τ (G) denote the smallest positive eigenvalue of $ A(G) $ A (G). In 1990, Pavlíková and Kr $ \breve{c} $ c ˘ -Jediný proved that among all nonsingular trees on n = 2m vertices, the comb graph (obtained by taking a path on m vertices and adding a new pendant vertex to every vertex of the path) has the maximum τ value. We consider the problem for unicyclic graphs. Let $ \mathscr {U} $ U denote the class of all connected bipartite unicyclic graphs with a unique perfect matching, and for each $ m\geq ~3 $ m ≥ 3 , let $ \mathscr {U}_n $ U n be the subclass of $ \mathscr {U} $ U with graphs on n = 2m vertices. We first obtain the classes of unicyclic graphs U in $ \mathscr {U} $ U such that $ \tau (U)\leq \sqrt {2}-1 $ τ (U) ≤ 2 − 1. We then find the unique graph $ U_o^n $ U o n (resp. $ U_e^n $ U e n ) having the maximum τ value among all graphs in $ \mathscr {U}_n $ U n when m is odd (resp. when m is even). Finally, we prove that $ U_o^6 $ U o 6 (the graph obtained from a cycle of order 4, by adding two pendants to two adjacent vertices) is the graph with maximum τ value among all graphs in $ \mathscr {U} $ U . As a consequence, we obtain a sharp upper bound for $ \tau (U) $ τ (U) when $ U\in \mathscr {U} $ U ∈ U . [ABSTRACT FROM AUTHOR]

The Susceptible–Infected–Susceptible (SIS) model in complex networks is one of the critical models employed in the modeling of virus spread. The study of the heterogeneous SIS model with a non-homogeneous nodal infection rate in finite-size networks has attracted little attention. Investigating the statistical properties of heterogeneous SIS epidemic dynamics in finite networks is thus intriguing. In this paper, we focus on the measure of variability in the number of infected nodes for the heterogeneous SIS epidemic dynamics in finite-size bipartite graphs and star graphs. Specifically, we investigate the metastable-state variance of the number of infected nodes for the SIS epidemic process in finite-size bipartite graphs and star graphs with heterogeneous nodal infection rates. We employ an extended individual-based mean-field approximation to analyze the heterogeneous SIS epidemic process in finite-size bipartite networks and star graphs. We derive the approximation solutions of the variance of the infected number. We verify the proposed theory by simulations. The proposed theory has the potential to help us better understand the fluctuations of SIS models like epidemic dynamics with a non-homogeneous infection rate. [ABSTRACT FROM AUTHOR]

For a graph G, let ik(G) be the number of independent sets of size k in G. The independence polynomial I(G; x) =∑k≥0ik(G)xk 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]

Consider a bipartite distance-regularized graph Γ with color partitions Y and Y ′ . Notably, all vertices in partition Y (and similarly in Y ′ ) exhibit a shared eccentricity denoted as D (and D ′ , respectively). The characterization of bipartite distance-regularized graphs, specifically those with D ≤ 3 , in relation to the incidence structures they represent is well established. However, when D = 4 , there are only two possible scenarios: either D ′ = 3 or D ′ = 4 . The instance where D = 4 and D ′ = 3 has been previously investigated. In this paper, we establish a one-to-one correspondence between the incidence graphs of quasi-symmetric SPBIBDs with parameters (v , b , r , k , λ 1 , 0) of type (k - 1 , t) , featuring intersection numbers x = 0 and y > 0 (where y ≤ t < k ), and bipartite distance-regularized graphs with D = D ′ = 4 . Moreover, our investigations result in the systematic classification of 2-Y-homogeneous bipartite distance-regularized graphs, which are incidence graphs of quasi-symmetric SPBIBDs with parameters (v , b , r , k , λ 1 , 0) of type (k - 1 , t) with intersection numbers x = 0 and y = 1 . [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]

The second largest eigenvalue of a graph is an important algebraic parameter which is related with the expansion, connectivity and randomness properties of a graph. Expanders are highly connected sparse graphs. In coding theory, Expander codes are Error Correcting codes made up of bipartite expander graphs. In this paper, first we prove the interlacing of the eigenvalues of the adjacency matrix of the bipartite graph with the eigenvalues of the bipartite quotient matrices of the corresponding graph matrices. Then we obtain bounds for the second largest and second smallest eigenvalues. Since the graph is bipartite, the results for Laplacian will also hold for Signless Laplacian matrix. We then introduce a new method called vertex-split of a bipartite graph to construct asymptotically good expander codes with expansion factor D/2 < α < D and ϵ < 1/2 and prove a condition for the vertex-split of a bipartite graph to be k-connected with respect to λ2. Further, we prove that the vertex-split of G is a bipartite expander. Finally, we construct an asymptotically good expander code whose factor graph is a graph obtained by the vertex-split of a bipartite graph. [ABSTRACT FROM AUTHOR]

A chain graph is a bigraph where the neighborhood of vertices in each part forms a chain under set inclusion. Chain graphs have received considerable attention from researchers in the field of spectral graph theory, as they have the maximum spectral radius among all the bigraphs of prescribed size and order. Nevertheless, the areas of some graph parameters remain untouched. The reciprocal Wiener index or the Harary index is one of the distance-based topological indices among several graph parameters designed to capture the different aspects of molecular structure. This article explores the Harary index of chain graphs, giving the bounds and other properties. Further, the Harary index of threshold graphs, a slight structural variant of chain graphs is also discussed. The main focus is on chain graphs with integer-valued Harary index. The article presents a quadratic time algorithm for the inverse Harary index problem for chain graphs and hence contributes significantly to the theory of inverse problems on topological indices. [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]

Let Δ be an (abstract) simplicial complex on n vertices. One can define the Artinian monomial algebra A (Δ) = k [ x 1 , ... , x n ] / 〈 x 1 2 , ... , x n 2 , I Δ 〉 , where k is a field of characteristic 0 and I Δ is the Stanley-Reisner ideal associated to Δ. In this paper, we aim to characterize the Weak Lefschetz Property (WLP) of A (Δ) in terms of the simplicial complex Δ. We are able to completely analyze when the WLP holds in degree 1, complementing work by Migliore, Nagel and Schenck on the WLP for quotients by quadratic monomials. We give a complete characterization of all 2-dimensional pseudomanifolds Δ such that A (Δ) satisfies the WLP. We also construct Artinian Gorenstein algebras that fail the WLP by combining our results and the standard technique of Nagata idealization. [ABSTRACT FROM AUTHOR]

Bipartite graphs can describe various systems in real world. In this study, we define a new problem class for optimizing the cost or profit associated with state changes in systems represented by bipartite graphs and propose a heuristic approach based on a fast greedy algorithm. We present the problem setting of the network circuit and device removal problem as a real-world problem and demonstrate the superiority of the proposed method for large-scale applications. This study contributes to the understanding and solving of various optimization problems in industrial fields, providing a comprehensive approach to cost (profit) optimization problems associated with state changes in systems represented by bipartite graphs.

The quest for content differentiation and audience engagement is paramount in the competitive landscape of Video-on-Demand (VOD) platforms. The paper proposes a system investigating VOD platform series data to recommend actors and themes to VOD vendors. To achieve this, we analyzed the storylines of 72 VOD movie series to extract keywords. Using these keywords, we generated a network using Social Network Analysis. By examining the network, we identified content gaps. After semantic clustering, we utilized TOPSIS to determine keywords with high centrality scores. These are a foundation for connecting peripheral keywords and generating new content. The paper’s findings suggest that the proposed content-based recommender system can help VOD platforms create innovative storylines by leveraging structural holes in a TV series content keyword graph. The study also suggests that successful directors take risks by combining different keywords from various network parts. This approach allows them to attract a wider range of audiences and increase their chances of success.