Search

• Novel impact metrics based on graph density. • Impact evaluation on large data sample. • Novel results not correlated with established metrics • Validation with commonly accepted ground-truth information. Traditionally, citation count has served as the main evaluation measure for a paper's importance and influence. In turn, many evaluations of authors, institutions and journals are based on aggregations upon papers (e.g. h-index). In this work, we explore measures defined on the citation graph that offer a more intuitive insight into the impact of a paper than the superficial count of citations. Our main argument is focused on the identification of influence as an expression of the citation density in the subgraph of citations built for each paper. We propose two measures that capitalize on the notion of density providing researchers alternative evaluations of their work. While the general idea of impact for a paper can be viewed as how many researchers have shown interest to a piece of work, the proposed measures are based on the hypothesis that a piece of work may have influenced some papers even if they do not contain references to that piece of work. The proposed measures are also extended to researchers and journals. [ABSTRACT FROM AUTHOR]

This paper presents results of topic modeling and network models of topics using the ICCS corpus, which contains domain-specific (computational science) papers over sixteen years (a total of 5695 papers). We discuss topical structures of ICCS, how these topics evolve over time in response to the topicality of various problems, technologies and methods, and how all these topics relate to one another. This analysis illustrates multidisciplinary research and collaborations among scientific communities, by constructing static and dynamic networks from the topic modeling results and the authors’ keywords. The results of this study give insights about the past and future trends of core discussion topics in computational science. We used the Non-negative Matrix Factorization(NMF) topic modeling algorithm to discover topics and labeled and grouped results hierarchically. We used Gephi to study static networks of topics, and an R library called DyA to analyze the dynamic networks of topics. [ABSTRACT FROM AUTHOR]

The gas diffusion layer (GDL) is considered one of the most significant components in the proton exchange membrane fuel cell (PEMFC). Its electrical impedance is crucial to the performance of power generation for PEMFC. The study of the conduction mechanism of the GDL substrate-carbon fiber paper(CFP) treated with PTFE is still a considerable challenge. This work reveals that the type and number of contact points are direct factors that affect CFP through-plane resistance. The CFP resistance along the through-plane direction is a function of the contact point density inside CFP, rather than traditional loading pressure. Based on the structural characteristics of CFP, a graph theory model that can express the complex three-dimensional structure and anisotropy of CFP is constructed instead of the finite element model or formula model—using the characterization of the distribution of PTFE in the CFP section. The accuracy of model prediction for the CFP resistance of 0 wt% and 20 wt% PTFE can reach 95% and 90%, respectively. This study provides a fundamental basis for the design and processing of CFP with lower electrical loss and is of great significance for further improving the power generation efficiency of PEMFC. Image 1 • A mechanism to explain the essential effect of PTFE on the conduction is proposed. • PTFE affects electrical resistance by changing the contact state of carbon fibers. • Graph theory model can be well used to simulate the conductivity of carbon paper. • There is huge potential for the reduction of electrical resistance in carbon paper. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents a novel dynamic causal digraph reasoning method for fault diagnosis and its application to the short circulation process of a paper machine. In order to improve the fault detection ability of the original causal digraph method, a residual modification approach that takes into account the direction of different fault effects is presented. An improvement of the isolation capability of the original method, an inference mechanism between the arcs of the graph, is also proposed to locate process faults on the arcs. The results from the application show that the proposed method, compared to the conventional method, is able to detect the correct nodes and to identify the responsible arcs when the system is affected by a process fault. [Copyright &y& Elsevier]

"Which graphs are determined by their spectra (DS for short)?" is an important and challenging topic in spectral graph theory. Let G be an n -vertex graph with adjacency matrix A (G) and adjacency walk matrix W A (G) = [ e , A (G) e , ... , A n − 1 (G) e ]. We call G controllable if the rank of W A (G) is n over R and noncontrollable otherwise. In Wang (2017), the author gave a simple condition for a controllable graph to be determined by their generalized adjacency spectrum (DGAS for short). However, the result fails for noncontrollable graphs. In this paper, we consider the problem in the context of the generalized distance spectrum. Let G be a connected graph with distance matrix D. A graph G is determined by its generalized distance spectrum (DG D S for short) if any graph H sharing the same generalized distance spectrum with G must be isomorphic to G. The paper aims to extend the result in Wang (2017) from generalized adjacency spectrum to generalized distance spectrum. Besides, a simple arithmetic criterion is given to determine whether a connected graph is DG D S or not, which is applicable to some kind of noncontrollable graphs, e.g., regular graphs. [ABSTRACT FROM AUTHOR]

The chromatic index , χ ′ (G) , is the smallest integer k for which a graph G has a proper edge coloring. The Classification Problem involves determining whether a graph G is Class 1 ( χ ′ (G) = Δ (G)) or Class 2 ( χ ′ (G) = Δ (G) + 1). It is known that subgraph-overfull graphs must be Class 2. In this paper we are concerned with the Classification Problem for split graphs G [ Q ∪ S ] where Q is a clique and S is an independent set. When Δ (G) is odd, G is known to be Class 1. The original proof presented by Chen et al. (1995) has a minor flaw which we detail in this paper while also clarifying that it does not compromise their result. We prove that their technique can be adapted in a non-trivial way to show that some split graphs with even Δ (G) are also Class 1. We show that to solve the Classification Problem for split graphs it suffices to consider that all vertices in Q have degree Δ (G). Considering the subset X of S of the vertices of degree at most Δ (G) / 2 , we show that if the neighborhood of X has at least ⌊ | Q | / 2 ⌋ vertices, then G is Class 1; in the remaining cases we characterize the subgraph-overfull split graphs. • Correction of a flaw in the proof that odd maximum degree split graphs are Class 1. • Proof that certain split graphs with even maximum degree are Class 1. • Characterization of the split graphs which are subgraph-overfull, and thus Class 2. [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]

An eigenvalue λ of a signed graph S of order n is a main eigenvalue if its eigenspace is not orthogonal to the all-ones vector j. Characterizing signed graphs with exactly k (1 ≤ k ≤ n) main eigenvalues is a problem in algebraic and graph theory that has been studied since 2020. Z. Stanić has noticed that a signed graph has exactly one main eigenvalue if and only if it is net-regular, and in this paper, we study signed graphs with exactly two distinct main eigenvalues by studying (0 , 1 , 2) -multi-graphs with exactly two distinct main eigenvalues. We partially characterize the case when the basic graphs of the (0 , 1 , 2) -multi-graphs are trees, and propose some problems for further research. [ABSTRACT FROM AUTHOR]

The proximity π = π (G) of a connected graph G is the minimum, over all vertices, of the average distance from a vertex to all others. Similarly, the maximum is called the remoteness and denoted by ρ = ρ (G). The concepts of proximity and remoteness, first defined in 2006, attracted the attention of several researchers in Graph Theory. Their investigation led to a considerable number of publications. In this paper we present a survey of the research work done to date. [ABSTRACT FROM AUTHOR]

• We review common conceptualizations of task-based functional connectivity. • Advances in multivariate analysis frameworks leads to more sensitive analyses. • Graph theory helps to characterize local and global properties of brain networks. • Physiological noise, linearity and stationarity assumptions, and level of analysis must be noted. Functional connectivity is conventionally defined by measuring the similarity between brain signals from two regions. The technique has become widely adopted in the analysis of functional magnetic resonance imaging (fMRI) data, where it has provided cognitive neuroscientists with abundant information on how brain regions interact to support complex cognition. However, in the past decade the notion of "connectivity" has expanded in both the complexity and heterogeneity of its application to cognitive neuroscience, resulting in greater difficulty of interpretation, replication, and cross-study comparisons. In this paper, we begin with the canonical notions of functional connectivity and then introduce recent methodological developments that either estimate some alternative form of connectivity or extend the analytical framework, with the hope of bringing better clarity for cognitive neuroscience researchers. [ABSTRACT FROM AUTHOR]

This paper investigates the controllability of impulsive systems with input delay and impulse delay and its applications in multi-agent networks. We adopt the geometric and algebraic analytical tools to establish some easily verified controllability conditions for the considered system model. First, the analytic solution of the considered system is established on every impulsive interval by using ordinary differential equation theory. Then, according to the solution derived, some sufficient complete controllability criteria are developed to reveal the role of the Gramian matrices in different subintervals. By introducing a row matrix of different kinds of Gramian matrices, a complete controllability condition that is proved to be necessary and sufficient is further obtained. By using the relevant geometric matrix theory, the derived algebraic controllability condition is then converted to a geometric one. On other hand, we introduce a multi-agent network with delayed input and impulse and investigate its controllability. By resorting to graph theory and matrix theory, several factors affecting the controllability of the considered multi-agent networks are investigated, such as the topology structure, the inner coupling matrix, and the dynamics of each agent. Finally, two numerical examples are worked out to verify the derived controllability criteria. • Controllability criteria relying on impulse and delay are established. • A Gramian-like controllability condition with less conservativeness is obtained. • Controllability of impulsive delayed multi-agent network is first studied. • Controllability conditions related to the network factors and dynamics are revealed. [ABSTRACT FROM AUTHOR]

• We introduce a graph theory model and utilize dispatchable STN to address the mission planning problem for deep space detectors. • The proposed algorithm efficiently decreases the network scale and streamline the computational workload. • Our proposed algorithm effectively tackles the challenge of dynamic mission scheduling to effectively handle emergencies. Deep space exploration activities can effectively promote the development and application of space technology, which holds significant scientific and strategic value. The multi-mission and long-period detector is executed in deep space, and numerous temporal constraints are generated by mission planning. Moreover, scheduled missions may face external uncertainties, hindering their smooth execution. Therefore, temporal constraint processing strategies that possess dynamic adjustment capabilities play a crucial role in ensuring the successful execution of deep space detectors. Existing methods primarily concentrate on investigating fixed mission series, with limited efficiency in planning. Specifically, these methods do not rigorously enforce temporal constraints and lack the capability to handle the disruptions caused by emergencies, which hinder the smooth execution of planned missions. In this paper, we propose a dynamic temporal constraints algorithm, aiming to efficiently plan missions subject to temporal constraints and let it possess a certain degree of dynamic adjust capability. The simulation results demonstrate the effective simplification of redundant temporal constraints in mission networks by the proposed algorithm. In comparison to the classical algorithm, the computation time exhibits a clear advantage. Furthermore, the proposed algorithm possesses the capability to perform local, small-scale dynamic adjustments in response to emergencies that may disrupt the normal execution of missions. Consequently, this research establishes a robust basis for addressing temporal constraints in deep space detectors. [ABSTRACT FROM AUTHOR]

• This paper studies the scaled consensus problem which is a generalization of usual consensus investigated in the literature. • Innovative impulsive control protocols are proposed to solve the problems of scaled consensus for multi-agent systems. • It also studied the scaled consensus problems of multi-agent systems subject to external perturbations. This paper studies scaled consensus problems of multi-agent systems under fixed and switched topologies. Firstly, the scaled consensus protocols are designed for solving consensus problems of multi-agent systems under fixed topologies. Secondly, the scaled consensus problems of multi-agent systems under switching topologies are considered. Thirdly, scaled consensus of multi-agent systems with external perturbations is investigated via impulsive mechanism. Using matrix theory, graph theory and Lyapunov algorithm, we can show that under appropriate conditions the scaled consensus problems can be solved. Moreover, our results show that the boundedness of the sampling period depending on scalar scales and degree of networks has strong impact for achieving scaled consensus of the systems. Some numerical examples are provided to illustrate the effectiveness of the theoretical results. [ABSTRACT FROM AUTHOR]

The traveling salesman problem (TSP) is one of the classic research topics in the field of operations research, graph theory and computer science. In this paper, we propose a generalized model of traveling salesman problem, denoted by generalized traveling salesman path problem. Let G = (V , E , c) be a weighted complete graph, in which c is a nonnegative metric cost function on edge set E , i.e., c : E → R +. The traveling salesman path problem aims to find a Hamiltonian path in G with minimum cost. Compared to the traveling salesman path problem, we are given extra vertex subset V ′ and edge subset E ′ in the problem proposed in this paper; its goal is to construct a path which traverses all the edges in E ′ while only needs to visit each vertex in V ′ exactly once. Based on integer programming, we give a mathematical model of the problem, and design a 1 + 5 2 -approximation algorithm for the problem by combining linear programming rounding strategy and a special graph structure. • In this paper, we consider a generalized model of traveling salesman problem. • Based on integer programming, we give a mathematical model of the problem. • Combining linear programming rounding strategy and a special graph structure, we propose a 1 + 5 2 -approximation algorithm. [ABSTRACT FROM AUTHOR]

Decentralized deep learning algorithms leverage peer-to-peer communication of model parameters and/or gradients over communication graphs among the learning agents with access to their private data sets. The majority of the studies in this area focus on achieving high accuracy, with many at the expense of increased communication overhead among the agents. However, large peer-to-peer communication overhead often becomes a practical challenge, especially in harsh environments such as for an underwater sensor network. In this paper, we aim to reduce communication overhead while achieving similar performance as the state-of-the-art algorithms. To achieve this, we use the concept of Minimum Connected Dominating Set from graph theory that is applied in ad hoc wireless networks to address communication overhead issues. Specifically, we propose a new decentralized deep learning algorithm called minimum connected Dominating Set Model Aggregation (DSMA). We investigate the efficacy of our method for different communication graph topologies with a small to large number of agents using varied neural network model architectures. Empirical results on benchmark data sets show a significant (up to 100X) reduction in communication time while preserving the accuracy or in some cases, increasing it compared to the state-of-the-art methods. We also present an analysis to show the convergence of our proposed algorithm. • Proposing a communication-efficient protocol for decentralized learning systems. • Finding valuable connections in the network to reduce communication overhead. • Hybrid of federated learning and gossiping methods. • Verifying the method performance for different networks, datasets, and models. • Preserving accuracy while reducing communication, even in large-scale networks. [ABSTRACT FROM AUTHOR]

We investigate two conjectured spectral graph theoretic strengthenings of Turán's theorem. Let μ 1 ≥ ... ≥ μ n denote the eigenvalues of a graph G with n vertices, m edges and clique number ω (G). The concise version of Turán's theorem is that n / (n − d) is a lower bound for the clique number ω (G) , where d is the average degree. Our first conjecture is that d can be replaced in this bound with s + , where s + is the sum of the squares of the positive eigenvalues. We prove this conjecture for triangle-free, weakly perfect and Kneser graphs and for almost all graphs. We have also used various software tools to search for a counter-example. Nikiforov proved a spectral version of Turán's theorem that μ 1 2 ≤ 2 m (ω (G) − 1) ω (G) , and Bollobás and Nikiforov conjectured that for G ≠ K n μ 1 2 + μ 2 2 ≤ 2 m (ω (G) − 1) ω (G). For our second conjecture, we propose that for all graphs (μ 1 2 + μ 2 2) in this inequality can be replaced by the sum of the squares of the ω (G) largest eigenvalues, provided they are positive. We prove the conjecture for weakly perfect, Kneser, and classes of strongly regular graphs. We also provide experimental evidence and describe how the bound can be applied. Liu and Ning [19] published a wide-ranging paper entitled "Unsolved Problems in spectral graph theory", and these two conjectures were placed second and fourth in their list of such problems. [ABSTRACT FROM AUTHOR]

Assume we inspect a specimen represented as a collection of points and our task is to learn a physical value associated with each point. However, performing a direct measurement is impossible since it damages the specimen. The alternative is to employ aggregate measuring techniques (e.g., CT or MRI), whereby measurements are taken over subsets of points, and the exact values at each point are subsequently extracted by computational methods. In the Minimum Surgical Probing problem (MSP) the inspected specimen is represented by a graph G and a vector ℓ ∈ R n that assigns a value ℓ i to each vertex i. An aggregate measurement (called probe) centred at vertex i captures its entire neighbourhood, i.e., the outcome of a probe at i is P i = ∑ j ∈ N (i) ∪ { i } ℓ j where N (i) is the open neighbourhood of vertex i. Bar-Noy et al. (2022) gave a criterion whether the vector ℓ can be recovered from the collection of probes P = { P v ∣ v ∈ V (G) } alone. However, there are graphs where the vector ℓ cannot be recovered from P alone. In these cases, we are allowed to use surgical probes. A surgical probe at vertex i returns ℓ i. The objective of MSP is to recover ℓ from P and G using as few surgical probes as possible. In this paper, we introduce the Weighted Minimum Surgical Probing (WMSP) problem in which a vertex i may have an aggregation coefficient w i , namely P i = ∑ j ∈ N (i) ℓ j + w i ℓ i . We show that WMSP can be solved in polynomial time. Moreover, we analyse the number of required surgical probes depending on the weight vector w. For any graph, we give two boundaries outside of which no surgical probes are needed to recover the vector ℓ. The boundaries are connected to the (Signless) Laplacian matrix. In addition, we consider the special case where w = 0 → and explore the range of possible behaviour of WMSP by determining the number of surgical probes necessary in certain graph families, such as trees and various grid graphs. [ABSTRACT FROM AUTHOR]

Graph theory is a powerful and essential tool for applied scientists and engineers in analyzing and designing algorithms for several problems. Graph theory has a vital role in complex systems, especially in computer sciences. Applications of graph theory can be found in many scientific disciplines such as operational research, engineering, life sciences, management sciences, coding, and computer science. In the literature, there are two algorithms for constructing decompositions for the circulant graphs C 2 r , r with 2 r vertices and r degree. For r , m ⩾ 2 , a circulant-balanced complete multipartite graph C mr , (m - 1) r is a generalization to C 2 r , r. Here, the major contributions are the generalization of the algorithms used for constructing the decompositions for the circulant graphs C 2 r , r to generalized algorithms that can be used for the decomposition of C mr , (m - 1) r that have mr vertices and (m - 1) r degree. These generalized algorithms manage us to decompose the circulant graphs C mr , (m - 1) r by different graph classes. The paper's novelty is demonstrated by the fact that it is the first to suggest general approaches for decomposing circulant-balanced complete multipartite graphs. The constructed results in the present paper are suitable for generating different codes and also have great importance in the design of experiments. [ABSTRACT FROM AUTHOR]

This paper presents and studies a generalization of the microscopic image reconstruction problem (MIR) introduced by Frosini and Nivat (2007) and Nivat (2002). Consider a specimen for inspection, represented as a collection of points typically organized on a grid in the plane. Assume each point x has an associated physical value ℓ x , which we would like to determine. However, it might be that obtaining these values precisely (by what we call a surgical probe) is difficult, risky, or impossible. The alternative is to employ aggregate measuring techniques (such as EM, CT, US or MRI), whereby each measurement is taken over a larger window, and the exact values at each point are subsequently extracted by computational methods. In this paper, we extend the MIR framework in a number of ways. First, we consider a generalized setting where the inspected object is represented by an arbitrary graph G , and the vector ℓ ∈ R n assigns a value ℓ v to each node v. A probe centred at a node v will capture a window encompassing its entire neighbourhood N [ v ] , i.e., the outcome of a probe centred at v is P v = ∑ w ∈ N [ v ] ℓ w . We give a criterion for the graphs for which the extended MIR problem can be solved by extracting the vector ℓ from the collection of probes, P = { P v ∣ v ∈ V }. We then consider cases where such reconstruction is impossible (namely, graphs G for which the probe vector P is inconclusive, in the sense that there may be more than one vector ℓ yielding P). Assume that surgical probes are technically available, yet are expensive or risky, and must be used sparingly. We show that in such cases, it may still be possible to achieve reconstruction based on a combination of a collection of ordinary (aggregate) probes together with a suitable set of surgical probes. We aim at identifying the minimum number of surgical probes necessary for a unique reconstruction, depending on the graph topology. This is referred to as the Minimum Surgical Probing problem (MSP). Besides providing a solution for the above problems for arbitrary graphs, we also explore the range of possible behaviours of the Minimum Surgical Probing problem by determining the number of surgical probes necessary in certain specific graph families, such as perfect k -ary trees, paths, cycles, grids, tori, tubes and hypercubes. [ABSTRACT FROM AUTHOR]

In Vukićević and Stevanović (2013), Theorem 2 is erroneous when m = 3 k + 1 for some integer k . The correct one is given now. That is, P I ( G ) ≥ m 2 − 3 m + 2 when m = 3 k + 1 for some integer k , where G is a connected bicyclic graph with m edges. [ABSTRACT FROM AUTHOR]

• Proposing a recognition scheme based on the combination of IEC 61850 and K-means. • Propose a region delineation method that can identify only unknown regions. • Propose a configuration method for phase-line relationships. • Improving k-means clustering accuracy. • Identify only unknown areas to avoid wasting resources. Accurate phase line topology identification of LV lines facilitates the handling of line faults, which is of great significance for the safe and stable operation of distribution networks. In this paper, we model and analyze the LV lines based on graph theory, and propose a phase line relationship identification scheme based on the combination of HPLC and k-means clustering for the problem of missing or dynamically changing phase line relationships of LV lines in the station area. Aiming at the known phase-line relationship in the station area such as distribution panel, two phase-line configuration schemes, Terminal extension and new phase-line description logical node PPLD, are proposed. The area is divided by combining the configuration information of IEC 61850 SCL and the information of metering automation system. If HPLC is configured in the unknown region, HPLC is used to identify the phase line relationship. If HPLC is not configured, k-means based algorithm is used for correlation analysis between voltage measurements. Example results from a place in Shandong show that the accuracy of the method proposed in this paper is 93.96 % on average, which is higher compared to the existing methods. Significance: Accurate identification of phase-line relationships in LV lines is essential for optimising load through phase-change switches. In this study, we propose a novel phase line relationship identification scheme that combines HPLC and k-means algorithm based on the existing equipment in the station area. Leveraging the known topology within the existing equipment (LTU, switchboard, etc.) in the station area, we introduce two phase line configuration schemes, Terminal extension (extending the known phase line relationship) and the new phase line description logical node PPLD (a novel approach for configuring known phase line relationships). Additionally, we suggest a method of regional division to recognise phase line relationships in unknown regions. If HPLC is configured, it is used for phase line identification; otherwise, a k-means based algorithm analyses voltage measurements. By tailoring identification schemes to the actual characteristics of the station area, we significantly reduce the amount of data to be identified, improving accuracy and resource efficiency. [Display omitted] [ABSTRACT FROM AUTHOR]

• The model of the cyber-physical-transportation network is established. • A two-stage model is applied to enhance the resilience for power system. • The accurate model of restoration time of faulty components is presented. • The load recovery model of cyber-physical is established. In this paper, a two-stage collaborative stochastic optimization method for pre-disaster emergency repair station planning and post-disaster recovery strategy of cyber-physical-transportation networks is proposed in this paper to enhance the resilience under extreme scenarios. In the first stage, based on the principle of hierarchical portioning, the responsible area for the emergency repair station is divided by the community theory, and the emergency repair station planning model is developed. In the second stage, the time sequence of repairing the faulty components is first established based on the graph theory. Then, based on the spatial distribution of adjacent time-series faulty components on the transportation network, a faulty component restoration time model is established to accurately reflect the faulty restoration time. On this basis, the functional coupling effects of economic dispatch control and substation automation system failures on load recovery are analyzed to establish a load recovery model. The case studies of the IEEE RTS-79 test system demonstrate that, compared with traditional independent recovery model, the model proposed in this paper performs better in enhancing resilience under extreme scenarios. [ABSTRACT FROM AUTHOR]

• This paper introduces the basic concept of graph theory, reviews the properties of Laplacian matrix and the traditional graph cuts method. Starting from four aspects in the realization process of spectral clustering (construction of similarity matrix, establishment of Laplacian matrix, selection of eigenvectors, and determination of the number of clusters), we have summarized in detail some representative algorithms in recent years. • Some successful applications of spectral clustering are summarized. In each aspect, the shortcomings of spectral clustering and some representative improved algorithms are emphatically analyzed. • This paper comprehensively analyzes some research on spectral clustering that has not yet been in-depth, and gives prospects on some valuable research directions. Spectral clustering converts the data clustering problem to the graph cut problem. It is based on graph theory. Due to the reliable theoretical basis and good clustering performance, spectral clustering has been successfully applied in many fields. Although spectral clustering has many advantages, it faces the challenges of high time and space complexity when dealing with large scale complex data. Firstly, this paper introduces the basic concept of graph theory, reviews the properties of Laplacian matrix and the traditional graph cuts method. Then, it focuses on four aspects of the realization process of spectral clustering, including the construction of similarity matrix, the establishment of Laplacian matrix, the selection of eigenvectors and the determination of the number of clusters. In addition, some successful applications of spectral clustering are summarized. In each aspect, the shortcomings of spectral clustering and some representative improved algorithms are emphatically analyzed. Finally, the paper comprehensively analyzes some research on spectral clustering that has not yet been in-depth, and gives prospects on some valuable research directions. [ABSTRACT FROM AUTHOR]

This paper is concerned with a conflict that N -pursuers versus M -evaders. It is a multi-pursuer multi-evader game extended from classical differential game theory to simultaneously address target selection and multi-player pursuit-evasion. Every pursuer attempts to intercept the evader it has chosen as its target while every evader does the opposite. This is modeled as a multi-player nonzero-sum differential game under a weighted directed graph. Moreover, a novel and more practical framework, the Unique-Choice (UC) games framework, is provided. Hamilton–Jacobi–Isaacs (HJI) is used for solving the game to derive the optimal distributed control strategy for each player based on graph theory. An important but has not been extensively studied issue, target selection, is studied. Different from the former research, this paper proposes a more reasonable criterion for target selection which makes the cost of pursuers minimized. The pursuers are proven to intercept evaders successfully with the proposed optimal pursuit strategy. Several illustrative examples under two different cases are presented, and the results show that the cost of pursuers with the proposed target selection algorithm is the minimum of all results. [ABSTRACT FROM AUTHOR]

Graph theory has been a useful tool for logic programming in many aspects. In this paper, we propose an equivalent representation of multi-adjoint logic programs using hypergraphs, which are a generalization of classical graphs that allows the use of hypergraph theory in logic programming. Specifically, this representation has been considered in this paper to increase the level and flexibility of different termination results of the computation of the least model of fuzzy logic programs via the immediate consequence operator. Consequently, the least model of more general and versatile fuzzy logic programs can be obtained after finitely many iterations, although infinite programs or programs with loops and general aggregators will be considered. [ABSTRACT FROM AUTHOR]

Different from the normal nesting algorithm, common-edge nesting reduces the spacing between parts, improves the utilization rate of the sheet, and shortens the processing time. Although common-edge nested parts may be useful in theory, they are not practical for large-scale production due to their cutting limitations. Existing research either did not consider all common cutting constraints or used graph theory methods for global common cutting path planning. However, due to cutting thermal effects and sheet deformation, it is difficult to use global common cutting path planning in actual processing. Therefore, this paper proposes a cutting sequence optimization algorithm for common-edge nested parts that consider all cutting constraints and proposes an algorithm for generating and optimizing common cutting paths. Experiments show that the common cutting path optimization algorithm proposed in this paper can reduce about 70% of the air path compared with commercial software. Furthermore, comparison by optical microscopy shows that the quality of the actual machined part is not inferior to that of the part machined according to the cut path generated by the commercial software. • The proposed cutting sequence optimization algorithm considers the common edge omission and sheet deformation. • A fast algorithm for calculating the inclusion relationship between parts is proposed. • A robust machining path generation algorithm for common-edge nested parts is proposed. • The proposed common cutting path optimization algorithm reduces the 70 % air paths compared with commercial software. [ABSTRACT FROM AUTHOR]

This paper contains a discrete-time higher-order sliding mode control for achieving the formation of a 6-Degrees of Freedom (DOF) Quadcopter swarm using the concept of a discrete Multi-agent system (DMAS). A graph theory is used to represent the communication between the Quadcopters and a leader-follower approach of DMAS is used to design the discrete super-twisting (DST) protocol for the formation of a 6-DOF Quadcopter swarm. The DST protocol not only ensures robustness but also reduces the convergence time and the chattering during the formation process of Quadcopters in a swarm. The stability condition of the formation is also derived using the Lyapunov function. The protocol is validated for the formation of 5 Quadcopters in the given pattern. The simulation results show that the formation is achieved in a finite time. Further to show the efficacy of the DST formation protocol, the results are compared with the first-order discrete-time sliding mode controllers designed by switching type reaching law and non-switching type of reaching law. As the first-order discrete-time sliding mode controllers have a significant amount of quasi-sliding mode band (QSMB) in the sliding surface during the operations, the DST protocol of higher-order discrete-time sliding mode control is preferred. From the comparative analysis, it is inferred that the DST protocol performs better for the formation of a 6-DOF Quadcopter swarm. • A discrete super-twisting (DST) sliding mode protocol is designed for formation of Quadcopter swarm. • The leader-follower approach and graph theory are used to design the DST protocol for formation of Quadcopter swarm. • The DST protocol ensures robustness and less convergence time for formation of Quadcopter swarm. • The DST protocol outperforms the existing formation protocols for Quadcopter swarm. [ABSTRACT FROM AUTHOR]

Tether-nets are one of the most promising approaches for active removal of space debris. This paper investigated the collision dynamics of flexible nets with different configurations, the focus is on the selection of an optimal configuration with respect to collision dynamics. Firstly, the design method of net configuration is proposed based on undirected graph theory, and five flexible nets with different configurations are designed, including quadrilateral, pentagon, octagon, dodecagon and circle. Secondly, the collision dynamics model is presented and its effectiveness is verified via numerical simulations and ground experiments. Finally, collision dynamics of the five flexible nets are simulated based on the verified model and the differences of these nets are compared and analyzed. Comparison results show that the flexible net with octagon configuration has better collision dynamics than others according to the maximum deformation, stress, and energy dissipation during the collision process, which provided an optimal configuration of flexible nets for space debris removal. • A design method of net configuration based on undirected graph is proposed. • The collision dynamics model of flexible nets is proposed and verified. • The octagonal net has the best dynamic characteristics. [ABSTRACT FROM AUTHOR]

The problem of relative drift elimination between the satellites in the swarm is considered in the paper. The proposed decentralized control takes into account a communication constraint such as limited size of communication area. Only the satellites within the communication area can be identified by relative motion determination system. The control aim is to eliminate the mean relative drift between all the satellites inside the communication area. The purpose of the work is to study the performance of the proposed decentralized control algorithm. It is shown that the system matrix of differential equations for the vector of relative drifts is related to the Laplacian matrix of the communication graph. In the case of the connected swarm, all but one eigenvalues of the system are negative, and the remaining one is equal to zero. It means that all the relative drifts converge to the same value under the proposed control. The speed of convergence is defined by the minimum absolute eigenvalue that depends on the graph topology. The initial drift and the convergence speed make it possible to estimate the communication distance that provides the connectivity of the graph. Considering normally distributed errors of the initial velocity after the launch, it is possible to estimate the distance between any two satellites after the convergence. It allows us to estimate the communication distance that ensures the relative drift elimination between all the satellites in the swarm. The obtained estimations are validated using Monte Carlo simulations. In numerical simulations the swarm of 3U CubeSats in low-Earth orbit is considered. The decentralized control is implemented by differential aerodynamic drag via the change of cross-sectional area using onboard reaction wheels. • Problem of relative drift elimination between satellites in the swarm is considered. • The proposed decentralized control takes into account a limited communication area. • Estimation of the communication area size that guarantees convergence is derived. • Analytical estimation of communication distance is obtained using graph theory. • Performance of swarm control by differential drag is studied numerically. [ABSTRACT FROM AUTHOR]

The paper is devoted to investigating the quasi-synchronization issue of fractional-order multi-layer networks with mismatched parameters under delay-dependent impulsive feedback control. It is worth highlighting that fractional-order multi-layer networks with mismatched parameters, as the extension model for single-layer or two-layer ones, are constructed in this paper. Simultaneously, the intra-layer and inter-layer couplings are taken into consideration, which is more general and rarely considered in discussions of network synchronization. An extended fractional differential inequality with impulsive effects is given to establish the grounded framework and theory on the quasi-synchronization problem under delay-dependent impulsive feedback control. Moreover, in the light of the Lyapunov method and graph theory, two criteria for achieving the quasi-synchronization of fractional-order multi-layer networks with mismatched parameters are derived. Furthermore, exponential convergence rates as well as the bounds of quasi-synchronization errors are successfully deduced. Ultimately, the theoretical results are applied in a practical power system, and some illustrative examples are proposed to show the effectiveness of theoretical analysis. [ABSTRACT FROM AUTHOR]

In this paper we consider the seating couples problem with an even number of seats, which, using graph theory terminology, can be stated as follows. Given a positive even integer v = 2 n and a list L containing n positive integers not exceeding n , is it always possible to find a perfect matching of K v whose list of edge-lengths is L ? Up to now a (non-constructive) solution is known only when all the edge-lengths are coprime with v. In this paper we firstly present some necessary conditions for the existence of a solution. Then, we give a complete constructive solution when the list consists of one or two distinct elements, and when the list consists of consecutive integers 1 , 2 , ... , x , each one appearing with the same multiplicity. Finally, we propose a conjecture and some open problems. [ABSTRACT FROM AUTHOR]

The enumerative problem of spanning trees of graphs is one of the fundamental problems in the field of graph theory, which has attracted the attention of mathematicians and physicists. For a connected graph G , let T be a spanning tree of G. In this paper, we call T to be a pm - t r e e of G if T contains a perfect matching. Recently, Li and Yan (Applied Mathematics and Computation, 456 (2023), 128125.) gave an explicit expression for the number of pm-trees in linear hexagonal chains on the plane, cylinder and Möbius strip, respectively. In this paper, we extend the results above and obtain the explicit formula for the number of pm-trees in linear polygonal chains with n polygons of 4 k + 2 vertices on the plane, cylinder and Möbius strip, respectively. [ABSTRACT FROM AUTHOR]

This paper investigates fully distributed scaled non-negative edge-consensus problems of networked systems with actuator saturation and unmeasurable internal states. By using the adaptive control method, output-feedback-based low-gain technique, and graph theory, a new adaptive algorithm is designed to obtain scaled edge-consensus conditions, under which the difficulties caused by the constraints on edge states and controllers are overcome. There are three interesting characteristics that any global information of networks is not used in this paper's algorithm and result, including the number of vertexes and edges; the feasible solutions of the scaled edge-consensus conditions exist and can be easily obtained; the convergence rate of the controller is adjustable. Furthermore, the designed algorithm is expanded in the cases without actuator saturation. Finally, three examples are given to verify the theoretical results. [ABSTRACT FROM AUTHOR]

A fan, denoted by H 2 k , is the graph obtained by joining a vertex to a path with 2 k vertices. A graph is H 2 k -free if it does not contain a subgraph H 2 k. Yuan (2021) [13] proved the Turán number and the extremal graphs of H 2 k -free graphs. In this paper, we characterize spectral extremal graphs of H 2 k -free graphs for sufficiently large n and k ≥ 3. • Spectral Turán-type problem is a frontier research field in spectral graph theory. In this paper, we characterize spectral extremal graphs of H 2 k -free graphs for sufficiently large n and k ≥ 3. • The problem investigated in this paper is very interesting and important in spectral graph theory. [ABSTRACT FROM AUTHOR]

A bi-coset graph Γ (G ; H , K) is a bipartite graph with the two vertex sets consisting of the cosets of subgroups H , K of a group G , and the adjacency determined by non-empty intersection. Bi-coset graphs constitute a classical object of algebraic graph theory and have been studied in various contexts (often with regard to their symmetries). In this paper, bi-coset graphs are revisited with the aim of using them in connection with the Cage Problem, the problem of finding a smallest k -regular graph of girth g , and with its generalization, the problem of finding a smallest biregular graph of girth g with vertices of degrees m , n. The girth of a bi-coset graph is shown to be related to the existence of special alternating sequences of elements from H and K , and k -regular bi-coset graphs of arbitrary large girths are shown to exist for all k ≥ 2. Bi-coset graphs are shown to be particularly suitable for constructions of bipartite biregular graphs which are biregular graphs in which each of the two sets making the graph bipartite consists of vertices of the same degree. A few bipartite biregular bi-coset graphs found in the paper are shown to be of the smallest order among all bipartite biregular graphs with the same parameters. Interestingly, one of our constructions starts from prime pairs of the form p , 6 p + 1. [ABSTRACT FROM AUTHOR]

• Mathematical foundations and key application areas of graph theory are reviewed. • Popular applications are state estimation, performance evaluation, optimization, and critical segment identification. • Data availability limits exploration and application of WDNs' topological patterns. • Combination of graph theory and hydraulic information leads to better results. • Challenges include tailoring topological indicators and integrating with GNNs. Graph theory (GT) and complex network theory play an increasingly important role in the design, operation, and management of water distribution networks (WDNs) and these tasks were originally often heavily dependent on hydraulic models. Facing the general reality of the lack of high-precision hydraulic models in water utilities, GT has become a promising surrogate or assistive technology. However, there is a lack of a systematic review of how and where the GT techniques are applied to the field of WDNs, along with an examination of potential directions that GT can contribute to addressing WDNs' challenges. This paper presents such a review and first summarizes the graph construction methods and topological properties of WDNs, which are mathematical foundations for the application of GT in WDNs. Then, main application areas, including state estimation, performance evaluation, partitioning, optimal design, optimal sensor placement, critical components identification, and interdependent networks analysis, are identified and reviewed. GT techniques can provide acceptable results and valuable insights while having a low computational burden compared with hydraulic models. Combining GT with hydraulic model significantly enhances the performance of analysis methods. Four research challenges, namely reasonable abstraction, data availability, tailored topological indicators, and integration with Graph Neural Networks (GNNs), have been identified as key areas for advancing the application and implementation of GT in WDNs. This paper would have a positive impact on promoting the use of GT for optimal design and sustainable management of WDNs. [Display omitted] [ABSTRACT FROM AUTHOR]

Abstract: A simple graph is reflexive if its second largest eigenvalue does not exceed 2. A graph is treelike (sometimes also called a cactus) if all its cycles (circuits) are mutually edge-disjoint. In a lot of cases one can establish whether a given graph is reflexive by identifying and removing a single cut-vertex (Theorem 1). In this paper we prove that, if this theorem cannot be applied to a connected treelike reflexive graph G and if all its cycles do not have a common vertex (do not form a bundle), such a graph has at most five cycles (Theorem 2). On the same conditions, in Theorem 3 we find all maximal treelike reflexive graphs with four and five cycles. [Copyright &y& Elsevier]

A classic result in extremal graph theory, known as Mantel's theorem, states that every non-bipartite graph of order n with size m > ⌊ n 2 4 ⌋ contains a triangle. Lin, Ning and Wu [Comb. Probab. Comput. 30 (2021) 258-270] proved a spectral version of Mantel's theorem for given order n. Zhai and Shu [Discrete Math. 345 (2022) 112630] investigated a spectral version for fixed size m. In this paper, we prove Q -spectral versions of Mantel's theorem. [ABSTRACT FROM AUTHOR]

The availability of industrial network topologies is limited, which presents a significant challenge for researchers in this field. Network generators are essential tools for generating realistic simulation outcomes in network research. Thus, it is crucial to use realistic topologies that can accurately represent the characteristics of the target network. The primary objective of this study is to address the existing research gap by developing an industrial network topology generator for novel topology datasets specific to industrial networks and the industrial Internet of Things (IIoT). In this paper, we describe the development of the graph theoretic ind ustrial topology gen erator (GENIND), a topology generator that can produce realistic IIoT and industrial network topologies. The proposed GENIND network topology generator is validated through comparisons with real-world industrial network topologies. The evaluation framework assesses the performance of the proposed GENIND system using three main measures: the overall network structure, path-related factors, and resilience topological structure features. The results of the evaluation demonstrate a high degree of similarity between the graphs generated by the GENIND system and the real-world industrial networks used for comparison. This finding suggests that the generated graphs can be utilized as reliable tools to predict the behavior of industrial networks under various conditions. [ABSTRACT FROM AUTHOR]

This paper explores the phenomenon of functional upgrading in Global Value Chains (GVCs) by applying empirical techniques of Social Network Analysis and graph theory to data from the TiVA database for the period from 1995 to 2018. Specifically, we focus on two (from less to more complex) stages of GVC participation: the global supply of manufacturing inputs and the global supply of business services to be embodied in other countries' exports. We identify which countries are the leading specialized global providers in each stage, analysing their evolutions over time and the relationship between both progressions. It highlights the trajectory of China that has increased its role as a hub in both stages to reach top positions. Using a dynamic panel data model, we find that the role of a country as a specialized global supplier of manufacturing inputs is associate with becoming a prominent global supplier of embodied business services, suggesting a path to functional upgrading in GVCs. [ABSTRACT FROM AUTHOR]

A graph is k -degenerate if every subgraph H has a vertex v with d H (v) ≤ k. The class of degenerate graphs plays an important role in the graph coloring theory. Observed that every k -degenerate graph is (k + 1) -choosable and (k + 1) -DP-colorable. Bernshteyn and Lee defined a generalization of k -degenerate graphs, which is called weakly k -degenerate. The weak degeneracy plus one is an upper bound for many graph coloring parameters, such as choice number, DP-chromatic number and DP-paint number. In this paper, we give two sufficient conditions for a plane graph without 4- and 6-cycles to be weakly 2-degenerate, which implies that every such graph is 3-DP-colorable and near-bipartite, where a graph is near-bipartite if its vertex set can be partitioned into an independent set and an acyclic set. [ABSTRACT FROM AUTHOR]

The recent years have witnessed the explosive application of sequencing technologies to study tumor–microenvironment interactions and their role in shaping intratumoral heterogeneity, neoplastic progression and tumor resistance to anticancer drugs. Statistical modeling is an essential tool to decipher the function of cellular interactions from massive amounts of transcriptomic data. However, most available approaches can only capture the existence of cell interconnections, failing to reveal how cells communicate with each other in (bi)directional, signed, and weighted manners. Widely used ligand–receptor signaling analysis can discern pairwise or dyadic cell–cell interactions, but it has little power to characterize the rock–paper–scissors cycle of interdependence among a large number of interacting cells. Here, we introduce an emerging statistical physics theory, derived from the interdisciplinary cross-pollination of ecosystem theory, allometric scaling law, evolutionary game theory, predator–prey theory, and graph theory. This new theory, coined quasi-dynamic game-graph theory (qdGGT), is formulated as generalized Lotka–Volterra predator–prey equations, allowing cell–cell crosstalk networks across any level of organizational space to be inferred from any type of genomic data with any dimension. qdGGT can visualize and interrogate how genes reciprocally telegraph signals among cells from different biogeographical locations and how this process orchestrates tumor processes. We demonstrate the application of qdGGT to identify genes that drive intercellular cooperation or competition and chart mechanistic cell–cell interaction networks that mediate the tumor–microenvironment crosstalk. [ABSTRACT FROM AUTHOR]

This paper presents an optimal control design method for multi-satellite assembly in an elliptic orbit in close proximity operations considering input saturation constraints. Tschauner–Hempel (T–H) equations are utilized to model the relative motion dynamics of the satellites in the Local Vertical Local Horizontal (LVLH) frame of the target satellite, where every satellite in the assembly is modeled as a point mass. The communication topology between the satellites in the assembly is modeled using graph theory, where the graph has several nodes representing the satellites and several edges representing the data exchange direction. It is assumed that every satellite exchanges its states with a few neighbors in the team, where the neighbors of every satellite are prespecified and do not change during the mission. This graph is utilized to construct the global dynamic model of the assembly, in which every node is represented by the dynamic model of a single satellite. The local control law, which is applied to every satellite in the assembly, consists of a state feedback gain and a coupling gain. The state feedback gain is designed using the discrete-time periodic Riccati equation to guarantee the local stability of every satellite separately, while the coupling gain is selected to satisfy the Lyapunov condition to guarantee the global stability of the assembly. The invariant-set method is utilized to prove the stability of the global dynamic system that is subjected to symmetric input saturation. The precision and optimality of the proposed control law are successfully demonstrated by numerical nonlinear simulations in a MATLAB environment for a cubic formation satellite assembly. • Assembling multiple satellites into an elliptic orbit in a cubic configuration. • Controlling a discrete-time periodic multi-agent system. • Designing an optimal control system using the discrete-time periodic Riccati equation. • Analyzing the stability of a discrete-time periodic multi-agent system under input saturation. [ABSTRACT FROM AUTHOR]

In this paper, the group consensus problem is investigated for multi-agent systems (MASs) with hybrid characteristics and directed topological networks. Firstly, the dynamical model of hybrid multi-agent system (MAS) is constructed, which includes discrete time agents and continuous time agents. A class of distributed control protocols are put forward for hybrid MASs. Then, under fixed and directed topological networks, sufficient and necessary conditions for the realization of group consensus are provided on basis of matrix theory and graph theory. Finally, simulations examples are given to further verify the validity of our theoretical results. • The discrete and continuous dynamical models of hybrid MAS are built. • A kind of distributed control protocols are designed for hybrid MASs. • Sufficient and necessary conditions are given for the group consensus of hybrid MASs. [ABSTRACT FROM AUTHOR]

The paper considers the disadvantages of existing approaches to testing software and hardware data security tools in order to confirm compliance of the implemented functionality with the declared characteristics. It demonstrates the necessity of ensuring completeness and optimality of testing. The paper describes some testing approaches based on the development of mathematical models using the automata theory and ensuring completeness of testing, but leaving the question of its optimality open. It describes the approach proposed earlier by the authors, which ensures both completeness and optimality of testing using the graph theory. In accordance with this approach, the software and hardware data security tool is represented as a directed graph without loops or multiple edges. The graph vertices correspond to the states of the software or hardware component, and the directed edges correspond to the transitions of the data security tool from one state to another when performing non-target functions or security functions. On the basis of this approach, the authors propose an algorithm for solving the problem of testing software and hardware data security tools using a number of well-known algorithms on graphs. In the paper, it is substantiated that a solution to the problem of ensuring completeness and optimality of testing exists if and only if any vertex of the derived graph obtained by removing all unused vertices and edges either belongs to a directed chain or lies in a strongly connected component. Application of the proposed algorithm for solving the problem of testing one of the software and hardware security tools is considered, and the possibility of its application in practice is confirmed. [ABSTRACT FROM AUTHOR]