Search

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]

In matching theory, one of the most fundamental and classical branches of combinatorics, canonical decompositions of graphs are powerful and versatile tools that form the basis of this theory. However, the abilities of the known canonical decompositions, that is, the Dulmage–Mendelsohn, Kotzig–Lovász, and Gallai–Edmonds decompositions, are limited because they are only applicable to particular classes of graphs, such as bipartite graphs, or they are too sparse to provide sufficient information. To overcome these limitations, we introduce a new canonical decomposition that is applicable to all graphs and provides much finer information. This decomposition also provides the answer to the longstanding absence of a canonical decomposition that is nontrivially applicable to general graphs with perfect matchings. We focus on the notion of factor‐components as the fundamental building blocks of a graph; through the factor‐components, our new canonical decomposition states how a graph is organized and how it contains all the maximum matchings. The main results that constitute our new theory are the following: (i) a canonical partial order over the set of factor‐components, which describes how a graph is constructed from its factor‐components; (ii) a generalization of the Kotzig–Lovász decomposition, which shows the inner structure of each factor‐component in the context of the entire graph; and (iii) a canonically described interrelationship between (i) and (ii), which integrates these two results into a unified theory of a canonical decomposition. These results are obtained in a self‐contained way, and our proof of the generalized Kotzig–Lovász decomposition contains a shortened and self‐contained proof of the classical counterpart. [ABSTRACT FROM AUTHOR]

PERFECT MATCHING‐CUT is the problem of deciding whether a graph has a perfect matching that contains an edge‐cut. We show that this problem is NP‐complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite five‐regular graphs, for graphs of diameter three, and for bipartite graphs of diameter four. We show that there exist polynomial‐time algorithms for the following classes of graphs: claw‐free, P5 ${P}_{5}$‐free, diameter two, bipartite with diameter three, and graphs with bounded treewidth. [ABSTRACT FROM AUTHOR]

Given a graph G = (V,E) and a list of available colors L(v) for each vertex v ∈ V, where L(v) ⊆ {1, 2,..., k}, List k-Coloring refers to the problem of assigning colors to the vertices of G so that each vertex receives a color from its own list and no two neighboring vertices receive the same color. The decision version of the problem, List k-Coloring, is NP-complete even for bipartite graphs. As an application of list coloring problem we are interested in the Futoshiki Problem. Futoshiki is an NP-complete Latin Square Completion Type Puzzle. Considering Futoshiki puzzle as a constraint satisfaction problem, we first give a list coloring based algorithm for it which is efficient for small boards of fixed size. To thoroughly investigate the efficiency of our algorithm in comparison with a proposed backtracking-based algorithm, we conducted a substantial number of computational experiments at different difficulty levels, considering varying numbers of inequality constraints and given values. Our results from the extensive range of experiments indicate that the list coloring-based algorithm is much more efficient. [ABSTRACT FROM AUTHOR]

Let GS be the graph of order n and containing σ self-loops. The energy E(GS) of graph GS is defined as E(GS) = n∑i=1 | λi - σ/n |, where λ1, λ2, . . ., λn be the eigenvalues of the adjacency matrix of GS. Two non-isomorphic graphs G1 and G2 of the same order are said to be equienergetic if they have same energy. The proposed research is an effort to expand the concept of equienergetic graphs from simple graphs to graphs having self-loops. In the present work, we have obtained a pair of equienergetic graphs and the energy of complete graphs as well as complete bipartite graphs with self loops. [ABSTRACT FROM AUTHOR]

The identification of drug–target interaction (DTI) is crucial for drug discovery. However, how to reduce the graph neural network's false positives due to its bias and negative transfer in the original bipartite graph remains to be clarified. Considering that the impact of heterogeneous auxiliary information on DTI varies depending on the drug and target, we established an adaptive enhanced personalized meta-knowledge transfer network named Meta Graph Association-Aware Contrastive Learning (MGACL), which can transfer personalized heterogeneous auxiliary information from different nodes and reduce data bias. Meanwhile, we propose a novel DTI association-aware contrastive learning strategy that aligns high-frequency drug representations with learned auxiliary graph representations to prevent negative transfer. Our study improves the DTI prediction performance by about 3%, evaluated by analyzing the area under the curve (AUC) and area under the precision–recall curve (AUPRC) compared with existing methods, which is more conducive to accurately identifying drug targets for the development of new drugs. [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]

In this paper, we introduce an efficient and effective algorithm for Graph-based Semi-Supervised Learning (GSSL). Unlike other GSSL methods, our proposed algorithm achieves efficiency by constructing a bipartite graph, which connects a small number of representative points to a large volume of raw data by capturing their underlying manifold structures. This bipartite graph, with a sparse and anti-diagonal affinity matrix which is symmetrical, serves as a low-rank approximation of the original graph. Consequently, our algorithm accelerates both the graph construction and label propagation steps. In particular, on the one hand, our algorithm computes the label propagation in closed-form, reducing its computational complexity from cubic to approximately linear with respect to the number of data points; on the other hand, our algorithm calculates the soft label matrix for unlabeled data using a closed-form solution, thereby gaining additional acceleration. Comprehensive experiments performed on six real-world datasets demonstrate the efficiency and effectiveness of our algorithm in comparison to five state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

With the widespread adoption of metagenomic sequencing, new perspectives have emerged for studying microbial ecological networks, yielding metabolic evidence of interspecies interactions that traditional co‐occurrence networks cannot infer. This protocol introduces the integrated Network Analysis Pipeline 2.0 (iNAP 2.0), which features an innovative metabolic complementarity network for microbial studies from metagenomics sequencing data. iNAP 2.0 sets up a four‐module process for metabolic interaction analysis, namely: (I) Prepare genome‐scale metabolic models; (II) Infer pairwise interactions of genome‐scale metabolic models; (III) Construct metabolic interaction networks; and (IV) Analyze metabolic interaction networks. Starting from metagenome‐assembled or complete genomes, iNAP 2.0 offers a variety of methods to quantify the potential and trends of metabolic complementarity between models, including the PhyloMint pipeline based on phylogenetic distance‐adjusted metabolic complementarity, the SMETANA (species metabolic interaction analysis) approach based on cross‐feeding substrate exchange prediction, and metabolic distance calculation based on parsimonious flux balance analysis (pFBA). Notably, iNAP 2.0 integrates the random matrix theory (RMT) approach to find the suitable threshold for metabolic interaction network construction. Finally, the metabolic interaction networks can proceed to analysis using topological feature analysis such as hub node determination. In addition, a key feature of iNAP 2.0 is the identification of potentially transferable metabolites between species, presented as intermediate nodes that connect microbial nodes in the metabolic complementarity network. To illustrate these new features, we use a set of metagenome‐assembled genomes as an example to comprehensively document the usage of the tools. iNAP 2.0 is available at https://inap.denglab.org.cn for all users to register and use for free. Highlights: The updated integrated Network Analysis Pipeline (iNAP 2.0) is an advanced platform that facilitates the calculation of various metabolic complementarity and competition indices, including the PhyloMint index, SMETANA (species metabolic interaction analysis), and metabolic distance, as well as the construction and analysis of metabolic interaction networks.Innovatively, iNAP 2.0 uses the random matrix theory (RMT) approach to determine the threshold for metabolic interaction networks.PhyloMint PTM in iNAP 2.0 allows users to view potentially transferable metabolites between microbial interactions and integrate them as network nodes to construct a microbe‐metabolite bipartite network alongside the microbial interaction network. [ABSTRACT FROM AUTHOR]

Given positive integers k ≤ d and a finite field F , a set S ⊂ F d is (k, c)-subspace evasive if every k-dimensional affine subspace contains at most c elements of S. By a simple averaging argument, the maximum size of a (k, c)-subspace evasive set is at most c | F | d - k . When k and d are fixed, and c is sufficiently large, the matching lower bound Ω (| F | d - k) is proved by Dvir and Lovett. We provide an alternative proof of this result using the random algebraic method. We also prove sharp upper bounds on the size of (k, c)-evasive sets in case d is large, extending results of Ben-Aroya and Shinkar. The existence of optimal evasive sets has several interesting consequences in combinatorial geometry. We show that the minimum number of k-dimensional linear hyperplanes needed to cover the grid [ n ] d ⊂ R d is Ω d (n d (d - k) d - 1 ) , which matches the upper bound proved by Balko et al., and settles a problem proposed by Brass et al. Furthermore, we improve the best known lower bound on the maximum number of incidences between points and hyperplanes in R d assuming their incidence graph avoids the complete bipartite graph K c , c for some large constant c = c (d) . [ABSTRACT FROM AUTHOR]

The concept of Roman domination has been a subject of intrigue for more than two decades, with the fundamental Roman domination problem standing out as one of the most significant challenges in this field. This article studies a practically motivated generalization of this problem, known as the k-strong Roman domination. In this problem variant, defenders within a network are tasked with safeguarding any k vertices simultaneously, under multiple attacks. The aim is to find a feasible mapping that assigns a (integer) weight to each vertex of the input graph with a minimum sum of weights across all vertices. A function is considered feasible if any non-defended vertex, i.e. one labeled by zero, is protected by at least one of its neighboring vertices labeled by at least two. Furthermore, each defender ensures the safety of a non-defended vertex by imparting a value of one to it while retaining a one for themselves. To the best of our knowledge, this paper represents the first theoretical study on this problem. The study presents results for general graphs, establishes connections between the problem at hand and other domination problems, and provides exact values and bounds for specific graph classes, including complete graphs, paths, cycles, complete bipartite graphs, grids, and a few selected classes of convex polytopes. Additionally, an attainable lower bound for general cubic graphs is provided. [ABSTRACT FROM AUTHOR]

Rainbow antimagic coloring is the combination of antimagic labeling and rainbow coloring. The smallest number of colors induced from all edge weights of antimagic labeling is the rainbow antimagic connection number of G , denoted by rac (G). Given a graph G with vertex set V (G) and edge set E (G) , the function f from V (G) to { 1 , 2 , ... , | V (G) | } is a bijective function. The associated weight of an edge y z ∈ E (G) under f is w (y z) = f (y) + f (z). A path R in the vertex-labeled graph G is said to be a rainbow y − z path if for any two edges y z , y ′ z ′ ∈ E (R) it satisfies w (y z) ≠ w (y ′ z ′). The function f is called a rainbow antimagic labeling of G if there exists a rainbow y − z path for every two vertices y , z ∈ V (G). When we assign each edge y z with the color of the edge weight w (y z) , we say the graph G admits a rainbow antimagic coloring. In this paper, we show the new lower bound and exact value of the rainbow antimagic connection number of comb product of any tree and complete bipartite graph. [ABSTRACT FROM AUTHOR]

Sombor index of a graph G is defined by SO(G) = ∑uv∈E(G) √d² G(u) + d² G(v), where dG(v) is the degree of the vertex v of G. An r-degree graph is a graph whose degree sequence includes exactly r distinctive numbers. In this article, we study r-degree connected graphs with integer Sombor index for r ∈ {5, 6, 7}. We show that: if G is a 5-degree connected graph of order n with integer Sombor index then n ≥ 50 and the equality occurs if only if G is a bipartite graph of size 420 with SO(G) = 14830; if G is a 6-degree connected graph of order n with integer Sombor index then n ≥ 75 and the equality is established only for the bipartite graph of size 1080; and if G is a 7-degree connected graph of order n with integer Sombor index then n ≥ 101 and the equality is established only for the bipartite graph of size 1680. [ABSTRACT FROM AUTHOR]

The study of bipartite maps (or Grothendieck's dessins d'enfants) is closely connected with geometry, mathematical physics and free probability. Here we study these objects from their permutation factorization formulation using a novel character theory approach. We first present some general symmetric function expressions for the number of products of two permutations respectively from two arbitrary, but fixed, conjugacy classes indexed by \alpha and \gamma that produce a permutation with m cycles. Our next objective is to derive explicit formulas for the cases where \alpha corresponds to full cycles, i.e., one-face bipartite maps. We prove a far-reaching explicit formula, and show that the number for any \gamma can be iteratively reduced to that of products of two full cycles, which implies an efficient dimension-reduction algorithm for building a database of all these numbers. Note that the number for products of two full cycles can be computed by the Zagier-Stanley formula. Also, in a unified way, we easily prove the celebrated Harer-Zagier formula and Jackson's formula, and we may obtain explicit formulas for several new families as well. [ABSTRACT FROM AUTHOR]

Let G be a graph and let P n be a path on n vertices. A spanning subgraph H of G is called a { P 3 , P 4 , P 5 } -factor if every component of H is one of P 3 , P 4 and P 5 . In 1994, Wang (J Graph Theory 18(2):161–167, 1994) gave a sufficient and necessary condition to ensure that a bipartite graph contains a { P 3 , P 4 , P 5 } -factor. In this paper, we use an equivalent form of Wang-type condition to establish two sufficient conditions to ensure that there exists a { P 3 , P 4 , P 5 } -factor in a connected bipartite graph, in which one is based on the size, the other is based on the spectral radius of the bipartite graph. [ABSTRACT FROM AUTHOR]

Graph neural networks (GNNs) have indeed shown significant potential in the field of personalized recommendation. The core approach is to reorganize interaction data into a user–item bipartite graph, leveraging high-order connectivity between user and item nodes to enhance their representations. However, most existing methods only deploy graph neural networks on parallel interaction graphs and treat the information propagated from all neighbors as equivalent, failing to adaptively capture user preferences. Therefore, the representations obtained may contain redundant or even noisy information, leading to non-robustness and suboptimal performance. The recently proposed Multimodal Graph Attention Network (MGAT) disentangles personal interests at the granularity of modality, operating on individual modal interaction graphs while utilizing a gated attention mechanism to differentiate the impacts of different modalities on user preferences. However, MGAT merely uses averaging to fuse multimodal features, which might overlook unique or critical information within each modality. To address this issue, this paper proposes a multimodal preference-based graph attention network. Firstly, for each individual modality, a single-modality graph network is constructed by integrating the user–item interaction bipartite graph, enabling it to learn user preferences for that modality. GNNs are used to aggregate neighborhood information and enhance the representation of each node. Additionally, a GRU module is utilized to determine whether to aggregate neighborhood information, thereby achieving noise reduction. In addition, a lightweight complementary attention mechanism is proposed to fuse user and item representations learned from different modal graphs. The complementary attention mechanism can not only avoid information redundancy, but also alleviate the problem of modal loss to a certain extent, and ultimately input the fusion results into the prediction module. Experimental results on the MovieLens and TikTok datasets demonstrate the effectiveness of the multimodal information and attention fusion mechanism in improving recommendation accuracy. Compared to baseline state-of-the-art algorithms, the proposed model achieves significant improvements in the Precision@K, Recall@K, NDCG@K and AUC metrics. Our code is publicly available on GitHub: [https://github.com/Oasisway624/mgpat]. [ABSTRACT FROM AUTHOR]

Flexible list coloring was introduced by Dvořák, Norin, and Postle in 2019. Suppose 0≤ϵ≤1, G is a graph, L is a list assignment for G, and r is a function with nonempty domain D⊆V(G) such that r(v)∈L(v) for each v∈D (r is called a request of L). The triple (G,L,r) is ϵ‐satisfiable if there exists a proper L‐coloring f of G such that f(v)=r(v) for at least ϵ∣D∣ vertices in D. We say G is (k,ϵ)‐flexible if (G,L′,r′) is ϵ‐satisfiable whenever L′ is a k‐assignment for G and r′ is a request of L′. It was shown by Dvořák et al. that if d+1 is prime, G is a d‐degenerate graph, and r is a request for G with domain of size 1, then (G,L,r) is 1‐satisfiable whenever L is a (d+1)‐assignment. In this paper, we extend this result to all d for bipartite d‐degenerate graphs. The literature on flexible list coloring tends to focus on showing that for a fixed graph G and k∈N there exists an ϵ>0 such that G is (k,ϵ)‐flexible, but it is natural to try to find the largest possible ϵ for which G is (k,ϵ)‐flexible. In this vein, we improve a result of Dvořák et al., by showing d‐degenerate graphs are (d+2,1∕2d+1)‐flexible. In pursuit of the largest ϵ for which a graph is (k,ϵ)‐flexible, we observe that a graph G is not (k,ϵ)‐flexible for any k if and only if ϵ>1∕ρ(G), where ρ(G) is the Hall ratio of G, and we initiate the study of the list flexibility number of a graphG, which is the smallest k such that G is (k,1∕ρ(G))‐flexible. We study relationships and connections between the list flexibility number, list chromatic number, list packing number, and degeneracy of a graph. [ABSTRACT FROM AUTHOR]

The concepts of domination and topological index hold great significance within the realm of graph theory. Therefore, it is pertinent to merge these concepts to derive the domination index of a graph. A novel concept of the domination index is introduced, which utilizes the domination degree of a vertex. The domination degree of a vertex a is defined as the minimum cardinality of a minimal dominating set (MDS) that includes a. Methods to find a MDS containing a particular vertex is also discussed in the study. The notion of domination degree and domination index are studied for graphs like complete graphs, complete bipartite, r − partite graphs, cycles, wheels, paths, book graphs, windmill graphs, Kragujevac trees. The study is extended to operation in graphs. Inequalities involving domination degree and already established graph parameters are discussed. An application of domination degree is discussed in facility allocation in a city. [ABSTRACT FROM AUTHOR]

We propose a theory of social norms (or conventions) that implement substantial levels of inequality between men and women, ethnic groups, and classes and that persist over long periods of time despite being inefficient and not supported by formal institutions. Consistent with historical cases, we extend the standard asymmetric stochastic evolutionary game model to allow subpopulation sizes to differ and idiosyncratic rejection of a status quo convention to be intentional to some degree (rather than purely random as in the standard evolutionary models). In this setting, if idiosyncratic play is sufficiently intentional and the subordinate class is sufficiently large relative to the elite, then risk-dominated conventions that are both more unequal and inefficient relative to alternative conventions will be stochastically stable and may persist for long periods. We show that the same is true in a general bipartite network of the population if most of the subordinate groups interactions are local, while the elite is more "cosmopolitan". We apply the model to the evolution of wage conventions on the bipartite network of workers and employers, and find that an unequal monopsonistic wage convention is robust to the idiosyncratic play of workers that otherwise might displace it. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph. For an edge e = x y ∈ E , the closed neighbourhood of e, denoted by N G [ e ] or N G [ x y ] , is the set N G [ x ] ∪ N G [ y ] . A vertex set L ⊆ V is liar’s vertex-edge dominating set of a graph G = (V , E) if for every e i ∈ E , | N G [ e i ] ∩ L | ≥ 2 and for every pair of distinct edges e i and e j , | (N G [ e i ] ∪ N G [ e j ]) ∩ L | ≥ 3 . This paper introduces the notion of liar’s vertex-edge domination which arises naturally from some applications in communication networks. Given a graph G, the Minimum Liar’s Vertex-Edge Domination Problem (MinLVEDP) asks to find a liar’s vertex-edge dominating set of G of minimum cardinality. In this paper, we study this problem from an algorithmic point of view. We show that MinLVEDP can be solved in linear time for trees, whereas the decision version of this problem is NP-complete for general graphs, chordal graphs, and bipartite graphs. We further study approximation algorithms for this problem. We propose two approximation algorithms for MinLVEDP in general graphs and p-claw free graphs. On the negative side, we show that the MinLVEDP cannot be approximated within 1 2 (1 8 - ϵ) ln | V | for any ϵ > 0 , unless N P ⊆ D T I M E (| V | O (log (log | V |)) . Finally, we prove that the MinLVEDP is APX-complete for bounded degree graphs and p-claw-free graphs for p ≥ 6 . [ABSTRACT FROM AUTHOR]

We prove that for any r∈N$r\in \mathbb {N}$, there exists a constant Cr$C_r$ such that the following is true. Let F={F1,F2,⋯}$\mathcal {F}=\lbrace F_1,F_2,\dots \rbrace$ be an infinite sequence of bipartite graphs such that |V(Fi)|=i$|V(F_i)|=i$ and Δ(Fi)⩽Δ$\Delta (F_i)\leqslant \Delta$ hold for all i$i$. Then, in any r$r$‐edge‐coloured complete graph Kn$K_n$, there is a collection of at most exp(CrΔ)$\exp (C_r\Delta)$ monochromatic subgraphs, each of which is isomorphic to an element of F$\mathcal {F}$, whose vertex sets partition V(Kn)$V(K_n)$. This proves a conjecture of Corsten and Mendonça in a strong form and generalises results on the multi‐colour Ramsey numbers of bounded‐degree bipartite graphs. It also settles the bipartite case of a general conjecture of Grinshpun and Sárközy. [ABSTRACT FROM AUTHOR]

In bipartite networks, nodes are divided into two different sets (namely, a set of actors and a set of events), and edges exist only between actors and events. The degree sequence of bipartite graph models may contain sensitive information. Thus, it is desirable to release noisy degree sequence, not the original degree sequence, in order to decrease the risk of privacy leakage. In this article, we propose to release the degree sequence in general bipartite graphs by adding discrete Laplace noises, which satisfies differential privacy. We use the moment method to estimate the unknown model parameter. The resulted estimator satisfies differential privacy. We establish the consistency and asymptotic normality of the differentially private estimator when the number of nodes goes to infinity. Finally, we apply our theoretical results to the logistic model and the log -linear model. [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]

In this paper, we introduce several new construction techniques of linear complimentary dual (LCD) codes. First, we show that if a LCD code is fixed by a transitive automorphism group, then the punctured code is also LCD. We show that several important families such as anti-primitive BCH codes and extended Gabidulin codes are LCD. Finally relationships among self-dual codes, λ-orthogonal matrices and LCD codes are studied. As an application we give LCD codes from Paley-type bipartite graph and from punctured MacDonalds codes. Further, we give a bound on some LCD codes. [ABSTRACT FROM AUTHOR]

Network analysis has become a crucial tool in genetic research, enabling the exploration of associations between genes and diseases. Its utility extends beyond genetics to include the assessment of environmental factors. Unipartite network analysis is commonly used in genomics to visualize initial insights and relationships among variables. Syndromic diseases, such as metabolic syndrome, are characterized by the simultaneous occurrence of various signs, symptoms, and clinicopathological features. Metabolic syndrome encompasses hypertension, diabetes, obesity, and dyslipidemia, and both genetic and environmental factors contribute to its development. Given that relevant data often consist of distinct sets of variables, a more intuitive visualization method is needed. This study applied multipartite network analysis as an effective method to understand the associations among genetic, environmental, and disease components in syndromic diseases. We considered three distinct variable sets: genetic factors, environmental factors, and disease components. The process involved projecting a tripartite network onto a two-mode bipartite network and then simplifying it into a one-mode network. This approach facilitated the visualization of relationships among factors across different sets and within individual sets. To transition from multipartite to unipartite networks, we suggest both sequential and concurrent projection methods. Data from the Korean Association Resource (KARE) project were utilized, including 352,228 SNPs from 8840 individuals, alongside information on environmental factors such as lifestyle, dietary, and socioeconomic factors. The single-SNP analysis step filtered SNPs, supplemented by reference SNPs reported in a genome-wide association study catalog. The resulting network patterns differed significantly by sex: demographic factors and fat intake were crucial for women, while alcohol consumption was central for men. Indirect relationships were identified through projected bipartite networks, revealing that SNPs such as rs4244457, rs2156552, and rs10899345 had lifestyle interactions on metabolic components. Our approach offers several advantages: it simplifies the visualization of complex relationships among different datasets, identifies environmental interactions, and provides insights into SNP clusters sharing common environmental factors and metabolic components. This framework provides a comprehensive approach to elucidate the mechanisms underlying complex diseases like metabolic syndrome. [ABSTRACT FROM AUTHOR]

Parallel paths of interconnection networks have attracted much attention in parallel computing systems, they are studied in terms of disjoint paths in an undirected graph G. A k -disjoint path cover (k-DPC for short) of a graph G is a set of k (internally) disjoint paths that altogether cover every vertice of the graph. A bipartite graph H is one-to-one bi-k-DPC if there is a k-DPC between any pair of vertices in different partite sets. A bipartite graph is hamiltonian laceable if there exists a hamiltonian path between any pair of vertices in different partite sets. The n -dimensional leaf-sort graph C F n has many good properties, including bipartite, symmetry, vertex-transitive. In this paper, we prove that C F n has one-to-one bi- (⌈ 3 n 2 ⌉ − 2) -DPC between any two vertices x and y in C F n , where x , y in different partite sets, and C F n is hamiltonian laceable. [ABSTRACT FROM AUTHOR]

For any bipartite graph G with bipartition V 1 and V 2 , a t -container C t (u , v) is a set of t internally disjoint paths P 1 , P 2 , ... , P t between two vertices u ∈ V 1 and v ∈ V 2 in G , i.e., C t (u , v) = { P 1 , P 2 , ... , P t }. Moreover, if V (P 1) ∪ V (P 2) ∪ ⋯ ∪ V (P t) = V (G) then C t (u , v) is called a spanning t -container, denoted by C t s l (u , v). The length of C t s l (u , v) = { P 1 , P 2 , ... , P t } is l (C t s l (u , v)) = max { l (P i) | 1 ≤ i ≤ t }. Besides, G is spanning t -laceable if there exists a spanning t -container between any two vertices u ∈ V 1 and v ∈ V 2 in G. Assume that u ∈ V 1 and v ∈ V 2 are two distinct vertices in a spanning t -laceable graph G. Let D t s l (u , v) be the collection of all C t s l (u , v) 's. Define the spanning t -wide distance between u and v in G , d t s l (u , v) = min { l (C t s l (u , v)) | C t s l (u , v) ∈ D t s l (u , v) } , and the spanning t -wide diameter of G , D t s l (G) = max { d t s l (u , v) | u ∈ V 1 , v ∈ V 2 }. In particular, the spanning wide diameter of G is D κ s l (G) , where κ is the connectivity of G. In the paper we first provide the lower and upper bounds of the wide diameter of a bipartite graph, and then determine the exact values of the spanning wide diameters of the spider web networks S W (m , n) for n = 2 , 4. [ABSTRACT FROM AUTHOR]

We consider the control of decentralized learning dynamics for agents in an anticoordination network game. In the anticoordination network game, there is a preferred action in the absence of neighbors' actions, and the utility an agent receives from the preferred action decreases as more of its neighbors select the preferred action, potentially causing the agent to select a less desirable action. The decentralized dynamics that are based on the synchronous best-response dynamics converge for the considered payoffs. Given a convergent action profile, we measure anticoordination by the number of edges in the underlying graph that have at least one agent in either end of the edge not taking the preferred action. A designer wants to find an optimal set of agents to control under a finite budget in order to achieve maximum anticoordination (MAC) on game convergence as a result of the dynamics. We show that the MAC is submodular in expectation over all realizations of the payoff interaction constants in bipartite networks. The proof relies on characterizing well-behavedness of MAC instances for bipartite networks, and designing a coupling between the dynamics and another distribution preserving selection protocol, for which we can show the diminishing returns property. Utilizing this result, we obtain a performance guarantee for the greedy optimization of MAC. Finally, we provide a computational study to show the effectiveness of greedy node selection strategies to solve MAC on general bipartite networks. [ABSTRACT FROM AUTHOR]

In this paper, we present a new framework that exploits combinatorial optimization for efficiently generating a large variety of combinatorial objects based on graphs, matroids, posets, and polytopes. Our method is based on a simple and versatile algorithm for computing a Hamilton path on the skeleton of a 0/1-polytope conv(X), where X ⊆ {0, l}n. The algorithm uses as a black box any algorithm that solves a variant of the classical linear optimization problem min{w⋅x; | x ∈ X}, and the resulting delay, i.e., the running time per visited vertex on the Hamilton path, is larger than the running time of the optimization algorithm only by a factor of log n. When X encodes a particular class of combinatorial objects, then traversing the skeleton of the polytope conv(X) along a Hamilton path corresponds to listing the combinatorial objects by local change operations; i.e., we obtain Gray code listings. As concrete results of our general framework, we obtain efficient algorithms for generating all (c-optimal) bases and independent sets in a matroid; (c-optimal) spanning trees, forests, matchings, maximum matchings, and c-optimal matchings in a graph; vertex covers, minimum vertex covers, c-optimal vertex covers, stable sets, maximum stable sets, and c-optimal stable sets in a bipartite graph; as well as antichains, maximum antichains, c-optimal antichains, and c-optimal ideals of a poset. Specifically, the delay and space required by these algorithms are polynomial in the size of the matroid ground set, graph, or poset, respectively. Furthermore, all of these listings correspond to Hamilton paths on the corresponding combinatorial polytopes, namely the base polytope, matching polytope, vertex cover polytope, stable set polytope, chain polytope, and order polytope, respectively. As another corollary from our framework, we obtain an O(tLPlog n) delay algorithm for the vertex enumeration problem on 0/1-polytopes {x ∈ ℝn | Ax ≤ b}, where A ∈ ℝm x n and b ∈ ℝm, and tLP is the time needed to solve the linear program min{w⋅x | Ax ≤ b}. This improves upon the 25-year-old O(tLP n) delay algorithm due to Bussieck and Lübbecke. [ABSTRACT FROM AUTHOR]

We study the problems of counting copies and induced copies of a small pattern graph H in a large host graph G. Recent work fully classified the complexity of those problems according to structural restrictions on the patterns H. In this work, we address the more challenging task of analyzing the complexity for restricted patterns and restricted hosts. Specifically, we ask which families of allowed patterns and hosts imply fixed-parameter tractability, i.e., the existence of an algorithm running in time f(H) ⋅ |G|O(1) for some computable function f. Our main results present exhaustive and explicit complexity classifications for families that satisfy natural closure properties. Among others, we identify the problems of counting small matchings and independent sets in subgraph-closed graph classes Q as our central objects of study and establish the following crisp dichotomies as consequences of the exponential time hypothesis: (1) Counting k-matchings in a graph G ∈ Q is fixed-parameter tractable if and only if Q is nowhere dense. (2) Counting k-independent sets in a graph G ∈ Q is fixed-parameter tractable if and only if Q is nowhere dense. Moreover, we obtain almost tight conditional lower bounds if Q is somewhere dense, i.e., not nowhere dense. These base cases of our classifications subsume a wide variety of previous results on the matching and independent set problem, such as counting k-matchings in bipartite graphs (Curticapean, Marx; FOCS 14), in F-colorable graphs (Roth, Wellnitz; SODA 20), and in degenerate graphs (Bressan, Roth; FOCS 21), as well as counting k-independent sets in bipartite graphs (Curticapean et al.; Algorithmica 19). At the same time, our proofs are much simpler: using structural characterizations of somewhere dense graphs, we show that a colorful version of a recent breakthrough technique for analyzing pattern counting problems (Curticapean, Dell, Marx; STOC 17) applies to any subgraph-closed somewhere dense class of graphs, yielding a unified view of our current understanding of the complexity of subgraph counting. [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]

We studied encounters between Chaco tortoises (Chelonoidis chilensis) that are in a threatened state of conservation in Patagonia, Argentina, which constitutes the southern limit of their geographical distribution. We monitored six individuals during different behavioural periods of the year (mating, nesting, and brumation), recording 24 344 encounters after tagging the animals with GPS tags. Constructing bipartite networks of burrows and tortoises, in addition to their projections, we discovered a spatial clustering of the burrows. Moreover, our research revealed that as tortoises approach the brumation period they use fewer unique burrows, engage in less burrow sharing, and increasingly favour spending time in their preferred burrow. During the mating and nesting periods some burrows are shared, whereas this was not the case during the brumation period. We studied the daily interactions through proximity-based networks, accounting for the daytime encounters during the different annual behavioural periods. We found the highest network density during the mating period, decreasing to zero, as expected, for the brumation period, when tortoises remain in their burrows during both night and day. Male–male interactions were more probable during the post-brumation and mating periods. Moreover, the number of daily encounters after sharing a burrow for a given night was found to be significant, which could be an indication of social behaviour and memory. Performing numerical simulations, we found that the proximity-based network densities were much higher than expected by chance, which could be attributable to individual selection of preferred sites or could be indicative of social behaviour among these threatened reptiles. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new domination parameter called "Isolate Semitotal Domination". A set S of vertices in a graph G is said to be a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. A semitotal dominating set S of a graph G is said to be an "Isolate Semitotal Dominating set"(ISTD-set) of G if has at least one isolated vertex. The isolate semitotal domination number(ISTD-number). denoted by 7,t (G). is the minimum cardinality of an isolate semitotal dominating set of G. In this paper, we studied some basic properties of ISTD-set. Further, we characterize all connected graphs and trees for which the ISTD-number is n-1 and n-2. where nis the order of the graph. At last, we proved that the problem of finding the ISTD-number for bipartite graphs is NP-complete. [ABSTRACT FROM AUTHOR]