Search

Domination plays an indispensable role in graph theory. Various types of domination explore various types of applications. Equal-status people work together and interlace with each other easily. In this paper, the paired equitable domination of a graph, its inflated graph, and its complement of an inflated graph were studied. The relationship between the domination number of the graph, the equitable domination number, and the paired equitable domination number of complements of the inflated graph were established. Furthermore, we proved the Nordhaus–Gaddum-type inequality, that is, γ p r e (H) + γ p r e (H) ≤ 6 if H is a graph with m nodes where m ≡ 0 ,   2 (m o d   8) and d (a i) = (m/2) for all a i . The challenges and limitations of this parameter of paired equitable and equitable domination depends on the degree of the vertex of the graph. Practical applications are discussed in various fields and illustrated using the studied parameter. [ABSTRACT FROM AUTHOR]

This paper is part of a line of research devoted to developing a compositional and geometric theory of Group Equivariant Non-Expansive Operators (GENEOs) for Geometric Deep Learning. It has two objectives. The first objective is to generalize the notions of permutants and permutant measures, originally defined for the identity of a single "perception pair", to a map between two such pairs. The second and main objective is to extend the application domain of the whole theory, which arose in the set-theoretical and topological environments, to graphs. This is performed using classical methods of mathematical definitions and arguments. The theoretical outcome is that, both in the case of vertex-weighted and edge-weighted graphs, a coherent theory is developed. Several simple examples show what may be hoped from GENEOs and permutants in graph theory and how they can be built. Rather than being a competitor to other methods in Geometric Deep Learning, this theory is proposed as an approach that can be integrated with such methods. [ABSTRACT FROM AUTHOR]

Space robots have been playing an important role in space on-orbit operation missions. However, the traditional configuration of space robots only has a single function and cannot meet the requirements of different space missions, and the launch cost of space robots is very high. Thus, the reconfigurable modular space robot system that can carry multiple loads and own mission adaptability is of great significance. Based on the analysis of a robot space mission, combined with the existing reconfigurable robots, this paper develops a configuration design scheme for a modular reconfigurable space robot, and carries out the prototype design. According to the configuration characteristics of the module, the dynamic modeling of the space robot is based on the graph theory analysis and principle of virtual work. Related application scenarios are set up. Function and feasibility of the dynamic modeling methods are verified through assembly experimentation and dynamic simulation. [ABSTRACT FROM AUTHOR]

With the rapid development of the global economy and trade, the number of ships serving ports in China is increasing continuously. Port traffic is becoming busier, and ship behavior is more complex and changeable. The analysis of ship behavior patterns in port waters has become an urgent problem to improve the efficiency and safety of port areas. In this paper, through the full integration of ship trajectory and port geographic information, the behavior chain of a single ship across the whole process of entering and exiting the port is identified. The traffic complexities and dynamics can be further analyzed by grouping the movement patterns of large ships. Based on graph theory, the port areas can be described as a transportation network in which functional areas are nodes and fairways between different areas are edges. The traffic can be analyzed through the network structure characteristics, such as node degree, node weight, and edge weight, and by their similarities and differences. This methodology provides a quantitative analysis for exploring the behavior patterns of large ships as well as the various traffic complexities. A case study in Tianjin Port has been conducted to verify the proposed model. The results show that it can accurately analyze a ship behavior's regularity, occasion, and correlation. It provides a theoretical reference for the port to schedule and formulate emergency plans. [ABSTRACT FROM AUTHOR]

In this paper, we explore the consensus of positive networked systems with actuator faults. Firstly, the undirected and strongly connected topology is established with graph theory. The positive system theory is used to analyze the positive consensus of the closed-loop networked systems. State feedback gains are derived utilizing Algebraic Riccati Inequalities. Bounded multiplicative faults are regarded as uncertainties in the system matrix, while treating additive faults as external disturbances. Further, this transformation refocuses the analysis on the consensus problem with an L 2 -gain. Subsequently, the Genetic Algorithm is employed to optimize the L 2 performance criteria. Finally, the effectiveness of the proposed theory is validated through simulations involving both single-input electric circuit systems and multi-input networked systems. [ABSTRACT FROM AUTHOR]

Risk assessment is a vital part in project management. It is possible that experts may provide comprehensive linguistic preference information in distinct forms with respect to different aspects of the risk assessment problem in investment management. It is a challenge to model and deal with comprehensive linguistic preference assessments in multiple forms given by experts. In this regard, this paper defines the generalised probabilistic linguistic preference relation (GPLPR) to represent different forms of linguistic preference information in a unified structure. Then, a probability cutting method is proposed to simplify the representation of a GPLPR. Afterwards, a graph-theory-based method is developed to improve the consistency degree of a GPLPR. A group decision making method with GPLPRs is then proposed to carry on the risk assessment in project management. Discussions regarding the comparative analysis and managerial insights are given. [ABSTRACT FROM AUTHOR]

Let n ≥ 1 be a fixed integer. The main objective of this paper is to compute some topological indices and coindices that are related to the graph complement of the prime ideal sum (PIS) graph of Z n , where n = p α , p 2 q , p 2 q 2 , p q r , p 3 q , p 2 q r , and p q r s for the different prime integers p , q , r , and s. Moreover, we construct M-polynomials and C o M -polynomials using the P I S -graph structure of Z n to avoid the difficulty of computing the descriptors via formulas directly. Furthermore, we present a geometric comparison for representations of each surface obtained by M-polynomials and C o M -polynomials. Finally, we discuss the applicability of algebraic graphs to chemical graph theory. [ABSTRACT FROM AUTHOR]

Graphs possessing minimal dominating sets have potential applicability in computer science & engineering. In a graph G, a dominating set L meeting N(x)∩L = N(y)∩L for any x,y ∈ V\L is known as a binary locating-dominating set. Minimizing the cardinality of such a set in G would be called the binary location-domination number γl-d(G) of G. This paper considers regular and strongly-regular graphs to study their binary location-domination and global binary location-domination numbers. Being an NP-complete problem, it is natural to study this parameter for special families of graphs having combinatorial and geometrical importance. Exact values of γl-d(G) have been evaluated for complete graphs, cycles, complete bipartite graphs and the generalized Petersen graphs P(n,2), n ≥ 4 and P(n,4), ≥ 5 ≤ n ≡ 0 (mod 3) ≤. Certain tight upper and lower bounds are shown for the path graphs, generalized Petersen graph P(n,4), ≥ 5 ≤ n ≡ 1,2 (mod 3) ≤, prism graphs and two infinite families of strongly regular graphs known as the triangular graphs and the square grid graphs. Moreover, an integer linear programming (ILP) model has been employed via CPLEX solver to show tightness in the upper bounds. By studying the binary locating-dominating sets in the complements of some of the above families, we also study their global location-domination number. Some open problems which naturally arise from the study have been proposed at the end. [ABSTRACT FROM AUTHOR]

For a graph G, its atom-bond connectivity (ABC) index (respectively, atom-bond sum connectivity (ABS) index) is defined as the addition of the numbers... over all unordered pairs of adjacent vertices {vi, vj} of G, where di and dj denote the degrees of vi and vj, respectively. In this paper, sharp upper bounds on the ABC and ABS indices are derived. All the graphs that attain the obtained bounds are also completely characterized. [ABSTRACT FROM AUTHOR]

Graph theory (GT) is a mathematical field that involves the study of graphs or diagrams that contain points and lines to represent the representation of mathematical truth in a diagrammatic format. From simple graphs, complex network architectures can be built using graph operations. Topological indices (TI) are graph invariants that correlate the physicochemical and interesting properties of different graphs. TI deal with many properties of molecular structure as well. It is important to compute the TI of complex structures. The corona product (CP) of two graphs G and H gives us a new graph obtained by taking one copy of G and V G copies of H and joining the i th vertex of G to every vertex in the i th copy of H. In this paper, based on various CP graphs composed of paths, cycles, and complete graphs, the geometric index (GA) and atom bond connectivity (ABC) index are investigated. Particularly, we discussed the corona products P s ⨀ P t , C t ⨀ C s , K t ⊙ K s , K t ⊙ P s , and P s ⊙ K t and GA and ABC index. Moreover, a few molecular graphs and physicochemical features may be predicted by considering relevant mathematical findings supported by proofs. [ABSTRACT FROM AUTHOR]

As countries attach great importance to the ocean-going navigation capability of ships, the energy consumption of shipborne equipment has attracted much attention. Although energy consumption analysis is a guiding method to improve energy efficiency, it often ignores the dynamic characteristics of the system. However, the traditional dynamic analysis method hardly considers the energy consumption characteristics of the system. In this paper, a new type of electric-driven helicopter traction system is designed based on the ASIST system. Combined with power bond graph theory, a system dynamic modeling method that considers both dynamic and energy consumption characteristics is proposed, and simulation analysis is carried out. The results indicate that the designed traction system in this study displays high responsiveness, robust, steady-state characteristics, and superior energy efficiency. When it engages with helicopter-borne aircraft, it swiftly transitions to a stable state within 0.2 s while preserving an efficient speed tracking effect under substantial load force, and no significant fluctuations are detected in the motor rotation rate or the helicopter movement velocity. Moreover, it presents a high energy utilization rate, achieving an impressive energy utilization rate of 84% per single working cycle. Simultaneously, the proposed modeling methodology is validated as sound and effective, particularly apt for the dynamic and power consumption analysis of marine complex machinery systems, guiding the high-efficiency design of the transmission system. [ABSTRACT FROM AUTHOR]

The primary objective of document-level event extraction is to extract relevant event information from lengthy texts. However, many existing methods for document-level event extraction fail to fully incorporate the contextual information that spans across sentences. To overcome this limitation, the present study proposes a document-level event extraction model called Integration Across Texts and Reciprocal Feedback (IATRF). The proposed model constructs a heterogeneous graph and employs a graph convolutional network to enhance the connection between document and entity information. This approach facilitates the acquisition of semantic information enriched with document-level context. Additionally, a Transformer classifier is introduced to transform multiple event types into a multi-label classification task. To tackle the challenge of event argument recognition, this paper introduces the Reciprocal Feedback Argument Extraction strategy. Experimental results conducted on both our COSM dataset and the publicly available ChFinAnn dataset demonstrate that the proposed model outperforms previous methods in terms of F1 value, thus confirming its effectiveness. The IATRF model effectively solves the problems of long-distance document context-aware representation and cross-sentence argument dispersion. [ABSTRACT FROM AUTHOR]

In this paper, in the environment of Euclidean Jordan algebras, we establish some inequalities over the Krein parameters of a symmetric association scheme and of a strongly regular graph. Next, we define the modified Krein parameters of a strongly regular graph and establish some admissibility conditions over these parameters. Finally, we introduce some relations over the Krein parameters of a strongly regular graph. [ABSTRACT FROM AUTHOR]

This paper initiates the study of the mathematical aspects of the ad-hoc Lanzhou index. If G is a graph with the vertex set { x 1 , ... , x n } , then the ad-hoc Lanzhou index of G is defined by L z ˜ (G) = ∑ i = 1 n d i (n − 1 − d i) 2 , where d i represents the degree of the vertex x i . Several identities for the ad-hoc Lanzhou index, involving some existing topological indices, are established. The problems of finding graphs with the extremum values of the ad-hoc Lanzhou index from the following sets of graphs are also attacked: (i) the set of all connected ξ -cyclic graphs of a fixed order, (ii) the set of all connected molecular ξ -cyclic graphs of a fixed order, (iii) the set of all graphs of a fixed order, and (iv) the set of all connected molecular graphs of a fixed order. [ABSTRACT FROM AUTHOR]

The frequency and severity of natural disasters is surging, posing an urgent need for robust communication network infrastructure that is capable of withstanding these events. In this paper, we present a groundbreaking graph-theoretic system designed to evaluate and enhance network resilience in the face of natural disasters. Our solution harnesses the power of topological robustness metrics, integrating real-time weather data, geographic information, detailed network topology data, advanced resilience algorithms, and continuous network monitoring. The proposed scheme considers four major real-world U.S.-based network providers and evaluates their physical topologies against two major hurricanes. Our novel framework quantifies the important characteristics of network infrastructure; for instance, AT&T is identified to have fared better against Hurricane Ivan (57.98 points) than Hurricane Katrina (39.17 points). We not only provide current insights into network infrastructure resilience, but also uncover valuable findings that shed light on the performance of backbone U.S. networks during hurricanes. Furthermore, our findings provide actionable insights to enrich the overall survivability and functionality of communication networks, mitigating the adverse impacts of natural disasters on communication systems and critical services in terms of improving network resiliency via adding additional nodes and link or rewiring. [ABSTRACT FROM AUTHOR]

The overall purpose of this paper is to define a new metric on the spreadability of a disease. Herein, we define a variant of the well-known graph-theoretic burning number (BN) metric that we coin the contagion number (CN). We aver that the CN is a better metric to model disease spread than the BN as the CN concentrates on first time infections. This is important because the Centers for Disease Control and Prevention report that COVID-19 reinfections are rare. This paper delineates a novel methodology to solve for the CN of any tree, in polynomial time, which addresses how fast a disease could spread (i.e., a worst-cast analysis). We then employ Monte Carlo simulation to determine the average contagion number (ACN) (i.e., a mostlikely analysis) of how fast a disease would spread. The latter is analyzed on scale-free graphs, which are specifically designed to model human social networks (sociograms). We test our method on some randomly generated scale-free graphs and our findings indicate the CN to be a robust, tractable (the BN is NP-hard even for a tree), and effective disease spread metric for decision makers. The contributions herein advance disease spread understanding and reveal the importance of the underlying network structure. Understanding disease spreadability informs public policy and the associated managerial allocation decisions. [ABSTRACT FROM AUTHOR]

This paper is concerned with a generalization of the atom-bond sum-connectivity (ABS) index, devised recently in [A. Ali, B. Furtula, I. Redžepovíc, I. Gutman, Atom-bond sum-connectivity index, J. Math. Chem., 60 (2022), 2081--2093]. For a connected graph G with an order greater than 2, the general atom-bond sum-connectivity index is represented as ABS γ(G) and is defined as the sum of the quantities (1-2(dx +dy)-1)γ over all edges xy of the graph G, where dx and dy represent the degrees of the vertices x and y of G, respectively, and γ is any real number. For -10 ≤ γ ≤ 10, the significance of ABSγ is examined on the data set of octane isomers for predicting six selected physicochemical properties of the mentioned compounds; promising results are obtained when the approximated value of γ belongs to the set {-3, 1, 3}. The effect of the addition of an edge between two non-adjacent vertices of a graph under ABS γ is also investigated. Moreover, the graphs possessing the maximum value of ABS γ, with γ > 0, are characterized from the set of all connected graphs of a fixed order and a fixed (i) vertex connectivity not greater than a given number or (ii) matching number. [ABSTRACT FROM AUTHOR]

This paper describes the operations carried out to generate a georeferenced heritage inventory at a supra-municipal scale. The tool establishes links between its heritage elements based on the features and characteristics of the territory. The work has been carried out on the fluvial zone of the Lower Guadalquivir, an area of approximately 8500 km2 located in Andalusia in the south of Spain. The method used is based on the digital inventory of the Andalusian immovable historical heritage generated by the Andalusian Institute of Historical Heritage, in which more than 500 heritage assets in the study area are indexed. The work begins with the expansion and processing of these assets with the aim of reorganizing them and establishing new parameters in their classification schemes. Subsequently, a spatial analysis developed in a GIS environment detects relationships between heritage assets determined by the physical characteristics of the territory. These relationships are contrasted by historical research, and eight heritage networks in the territory are defined as a result. Finally, one of the networks is used to show how, from the graph theory, it is possible to investigate the detected links. Ultimately, it is discussed how this study allows us to move toward new models of the heritage management of territorial dimension and relational vocation. [ABSTRACT FROM AUTHOR]

One of the most recent advancements in graph theory is the use of a multidisciplinary approach to the investigation of specific structural dependent features, such as physico-chemical properties, biological activity and the entropy measure of a graph representing objects like a network or a chemical compound. The ability of entropy measures to determine both the certainty and uncertainty about objects makes them one of the most investigated topics in science along with its multidisciplinary nature. As a result, many formulae, based on vertices, edges and symmetry, for determining the entropy of graphs have been developed and investigated in the field of graph theory. These measures assist in understanding the characteristics of graphs, such as the complexity of the networks or graphs, which may be determined using entropy measures. In this paper, we derive formulae of entropy measures of an extensively studied family of the interconnection networks and classify them in terms of complexity. This is accomplished by utilizing all three tools, including analytical formulae, graphical methods and numerical tables. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we approach a method of clustering binary signature of image in order to create a clustering graph structure for building the content‐based image retrieval. First, the paper presents the segmentation method based on low‐level visual features including colour and texture of image. On the basis of segmented image, the paper creates binary signature to describe location, colour, and shape of interest objects. In order to match similar images, the paper presents a similarity measure between the images based on binary signature. From that, the paper proposes the method of clustering binary signature to quickly query similar images. At the same time, the graph data structure is built using the partition cluster technique and the rules of binary signatures' distribution of images. On the basis of data structure, we propose a graph creation algorithm, a cluster splitting/merging algorithm, and a similarity image retrieval algorithm. To illustrate the proposed theory, we build an image retrieval application and assess the experimental results on the image datasets including COREL (1,000 images), CBIR images (1,344 images), WANG (10,800 images), MSRDI (15,720 images), and ImageCLEF (20,000 images). [ABSTRACT FROM AUTHOR]

The increasingly complex economic and financial environment in which we live makes the management of liquidity in payment systems and the economy in general a persistent challenge. New technologies make it possible to address this challenge through alternative solutions that complement and strengthen existing payment systems. For example, interbank balancing and clearing methods (such as real-time gross settlement) can also be applied to private payments, complementary currencies, and trade credit clearing to provide better liquidity and risk management. The paper defines the concept of a balanced payment system mathematically and demonstrates the effects of balancing on a few small examples. It then derives the construction of a balanced payment subsystem that can be settled in full and therefore that can be removed in toto to achieve debt reduction and payment gridlock resolution. Using well-known results from graph theory, the main output of the paper is the proof--for the general formulation of a payment system with an arbitrary number of liquidity sources--that the amount of liquidity saved is maximum, along with a detailed discussion of the practical steps that a lending institution can take to provide different levels of service subject to the constraints of available liquidity and its own cap on total overdraft exposure. From an applied mathematics point of view, the original contribution of the paper is two-fold: (1) the introduction of a liquidity node with a store of value function in obligation-clearing; and (2) the demonstration that the case with one or more liquidity sources can be solved with the same mathematical machinery that is used for obligation-clearing without liquidity. The clearing and balancing methods presented are based on the experience of a specific application (Tetris Core Technologies), whose wider adoption in the trade credit market could contribute to the financial stability of the whole economy and a better management of liquidity and risk overall. [ABSTRACT FROM AUTHOR]

Machine learning in finance has been on the rise in the past decade. The applications of machine learning have become a promising methodological advancement. The paper's central goal is to use a metadata-based systematic literature review to map the current state of neural networks and machine learning in the finance field. After collecting a large dataset comprised of 5053 documents, we conducted a computational systematic review of the academic finance literature intersected with neural network methodologies, with a limited focus on the documents' metadata. The output is a meta-analysis of the two-decade evolution and the current state of academic inquiries into financial concepts. Researchers will benefit from a mapping resulting from computational-based methods such as graph theory and natural language processing. [ABSTRACT FROM AUTHOR]

In this, communication world, the Network Function Virtualization concept is utilized for many businesses, small services to virtualize the network node function and to build a block that may connect the chain, communication services. Mainly, Virtualized Network Function Forwarding Graph (VNF-FG) has been used to define the connection between the VNF and to give the best end-to-end services. In the existing method, VNF mapping and backup VNF were proposed but there was no profit and reliability improvement of the backup and mapping of the primary VNF. As a consequence, this paper offers a Hybrid Hexagon-Cost Efficient algorithm for determining the best VNF among multiple VNF and backing up the best VNF, lowering backup costs while increasing dependability. The VNF is chosen based on the highest cost-aware important measure (CIM) rate, which is used to assess the relevance of the VNF forwarding graph. To achieve optimal cost-efficiency, VNF with the maximum CIM is selected. After the selection process, updating is processed by three steps which include one backup VNF from one SFC, two backup VNF from one Service Function Chain (SFC), and two backup VNF from different SFC. Finally, this proposed method is compared with CERA, MinCost, MaxRbyInr based on backup cost, number of used PN nodes, SFC request utility, and latency. The simulation result shows that the proposed method cuts down the backup cost and computation time by 57% and 45% compared with the CER scheme and improves the cost-efficiency. As a result, this proposed system achieves less backup cost, high reliability, and low time consumption which can improve the Virtualized Network Function operation. [ABSTRACT FROM AUTHOR]

In this paper, Lp-convergence for weighted sums of arrays of rowwise extended negatively dependent (rowwise END) random variables are investigated and some sufficient conditions for convergence are established. Additionally, the relationships among the convergence rates, weights of the sums and the dominating sequence of the rowwise END arrays are in a sense revealed. The results obtained in this paper generalise some corresponding ones for independent and some dependent random variables. [ABSTRACT FROM AUTHOR]

Generalized trigonometric functions and generalized hyperbolic functions can be converted to each other by the duality formulas previously discovered by the authors. In this paper, we apply the duality formulas to prove dual pairs of Wilker-type inequalities, Huygens-type inequalities, and (relaxed) Cusa-Huygens-type inequalities for the generalized functions. In addition, multiple- and double-angle formulas not previously obtained are also given. [ABSTRACT FROM AUTHOR]

The evolution of the convergence among the European countries, including both Eurozone as well as non-Eurozone economies, is investigated in this paper. To do so, we construct correlation-based networks and study them by employing the Threshold Weighted-Minimum Dominating Set (TW–MDS) algorithm and analyzing standard quantitative performance graph theory metrics. Each country is represented by a network node, while the edges represent the cross-correlations calculated for a specific macroeconomic variable, for a given time window. To study the intertemporal evolution of the network's interconnections, we examine its structure in three consecutive time intervals: 1999–2004, 2005–2010 and 2011–2019. The empirical findings provide a mixed pattern. The European countries exhibit a common behavior over time for some macroeconomic variables, but not for all of them. [ABSTRACT FROM AUTHOR]

In order to detect multi-ship encounter situations and improve the safety of navigation, this paper proposed a model which was able to mine multi-ship encounter situations from Automatic identification system (AIS) data and analyze the encounter spatial-temporal process and make collision avoidance decisions. Pairwise encounters identification results and ship motion index were combined into a ship encounter graph network which can use the complex network theory to describe the encounter spatial-temporal process. Network average degree, network average distance and network average clustering coefficient were selected. Based on the recognition results of pairwise encounter identification results, a discrete multi-ship encounter network is constructed. The process of multi-ship encounters from simple to complex to simple is mined based on the process of average network degree from 0 to 0 to obtain a continuous spatial-temporal process. The results can be used for multi-ship encounter situation awareness, multi-ship collision avoidance decision-making and channel navigation evaluation, and also provide data for machine learning. Quaternary dynamic ship domain, fuzzy logic and the weighted PageRank algorithm were used to rank the whole network risk, which is critical to "key ship collision avoidance." This method overcame the problem that the traditional collision risk evaluation method is only applicable to the difference between two ships and ship perception. The risk rank combined with the artificial potential field method was used. Compared with the traditional artificial potential field method, this method has fewer turns and a smoother trajectory. [ABSTRACT FROM AUTHOR]

This paper applies a new technique for modal decomposition based solely on measurements to test systems and demonstrates the technique's capability for partitioning a power network, which determines the points of separation in an islanding strategy. The mathematical technique is called the Koopman mode analysis (KMA) and stems from a spectral analysis of the so-called Koopman operator. Here, KMA is numerically approximated by applying an Arnoldi-like algorithm recently first applied to power system dynamics. In this paper we propose a practical data-driven algorithm incorporating KMA for network partitioning. Comparisons are made with two techniques previously applied for the network partitioning: spectral graph theory which is based on the eigenstructure of the graph Laplacian, and slow-coherency which identifies coherent groups of generators for a specified number of low-frequency modes. The partitioning results share common features with results obtained with graph theory and slow-coherency-based techniques. The suggested partitioning method is evaluated with two test systems, and similarities between Koopman modes and Laplacian eigenvectors are showed numerically and elaborated theoretically. [ABSTRACT FROM PUBLISHER]

In this paper we generalise the notion of visibility from a point in an integer lattice to the setting of graph theory. For a vertex x of a graph G, we say that a set S ⊆ V (G) is an x-position set if for any y ∈ S the shortest x, y-paths in G contain no point of S \ {y}. We investigate the largest and smallest orders of maximum x-position sets in graphs, determining these numbers for common classes of graphs and giving bounds in terms of the girth, vertex degrees, diameter and radius. Finally we discuss the complexity of finding maximum vertex position sets in graphs. [ABSTRACT FROM AUTHOR]

Jones et al. (2015) introduced the notion of u-representable graphs, where u is a word over {1, 2} different from 22 ... 2, as a generalization of word-representable graphs. Kitaev (2016) showed that if u is of length at least 3, then every graph is u-representable. This indicates that there are only two nontrivial classes in the theory of u-representable graphs: 11-representable graphs, which correspond to word-representable graphs, and 12-representable graphs. This study deals with 12-representable graphs. Jones et al. (2015) provided a characterization of 12-representable trees in terms of forbidden induced subgraphs. Chen and Kitaev (2022) presented a forbidden induced subgraph characterization of a subclass of 12-representable grid graphs. This paper shows that a bipartite graph is 12-representable if and only if it is an interval containment bigraph. The equivalence gives us a forbidden induced subgraph characterization of 12-representable bipartite graphs since the list of minimal forbidden induced subgraphs is known for interval containment bigraphs. We then have a forbidden induced subgraph characterization for grid graphs, which solves an open problem of Chen and Kitaev (2022). The study also shows that a graph is 12-representable if and only if it is the complement of a simple-triangle graph. This equivalence indicates that a necessary condition for 12-representability presented by Jones et al. (2015) is also sufficient. Finally, we show from these equivalences that 12-representability can be determined in O(n²) time for bipartite graphs and in O(n(m + n)) time for arbitrary graphs, where n and m are the number of vertices and edges of the complement of the given graph. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a connected graph with the vertex-set V and the edgeset E. The subdivision graph S(G) of the graph G is obtained from G by adding a vertex in the middle of every edge of G. In this paper, we investigate some properties of the graphs S (G) and L(S (G)), where L(S (G)) is the line graph of S (G). We will see that S (G) and L(S (G)) inherit some properties of G. For instance, we show that if G Cn, then Aut(G) = Aut(L(S(G))) (as abstract groups), where Cn is the cycle of order n. [ABSTRACT FROM AUTHOR]

A coloring C = (V1,...,Vk) of G partitions the vertex set V (G) into independent sets Vi which are said to be color classes with respect to the coloring C. A vertex v is said to have a dominator (dom) color class in C if there is color class Vi such that v is adjacent to all the vertices of Vi and v is said to have an anti-dominator (anti-dom) color class in C if there is color class Vj such that v is not adjacent to any vertex of Vj. Dominator coloring of G is a coloring C of G such that every vertex has a dom color class. The minimum number of colors required for a dominator coloring of G is called the dominator chromatic number of G, denoted by χd(G). Global Dominator coloring of G is a coloring C of G such that every vertex has a dom color class and an anti-dom color class. The minimum number of colors required for a global dominator coloring of G is called the global dominator chromatic number of G, denoted by χgd(G). In this paper, we give a counterexample for the conjecture posed in [I. Sahul Hamid, M.Rajeswari, Global dominator coloring of graphs, Discuss. Math. Graph Theory 39 (2019), 325-339] that for a graph G, if Xgd(G) = 2χd(G), then G is a complete multipartite graph. We deduce upper and lower bound for the global dominator chromatic number of Mycielskian of the graph G in terms of dominator chromatic number of G. [ABSTRACT FROM AUTHOR]

A triangular tile latching system consists of a set Σ of equilateral triangular tiles with at least one latchable side and an attachment rule which permits two tiles to get latched along a latchable side. In this paper we determine the language generated by a triangular tile latching system in terms of planar graphs. [ABSTRACT FROM AUTHOR]

Given a graph G = (V, E), a function f: V → {0, 1, 2, 3, 4} is a triple Roman dominating function (TRDF) of G, for each vertex v ∈ V, (i) if f (v) = 0, then v must have either one neighbour in V4, or either two neighbours in V2 ∪ V3 (one neighbour in V3) or either three neighbours in V2, (ii) if f (v) = 1, then v must have either one neighbour in V3 ∪ V4 or either two neighbours in V2, and if f (v) = 2, then v must have one neighbour in V2 ∪ V3 ∪ V4. The triple Roman domination number of G is the minimum weight of an TRDF f of G, where the weight of f is v V f (v). The triple Roman domination problem is to compute the triple Roman domination number of a given graph. In this paper, we study the triple Roman domination problem. We show that the problem is NP-complete for the star convex bipartite and the comb convex bipartite graphs and is APX-complete for graphs of degree at most 4. We propose a linear-time algorithm for computing the triple Roman domination number of proper interval graphs. We also give an (2H (Δ(G) + 1) - 1)-approximation algorithm for solving the problem for any graph G, where Δ(G) is the maximum degree of G and H (d) denotes the first d terms of the harmonic series. In addition, we prove that for any ε > 0 there is no (1/4 - ε) ln |V |-approximation polynomial-time algorithm for solving the problem on bipartite and split graphs, unless NP ⊆ DTIME (|V |O(log log |V |)). [ABSTRACT FROM AUTHOR]

A total coloring of a graph G is an assignment of colors to all the elements (vertices and edges) of the graph in such a way that no two adjacent or incident elements receive the same color. The total chromatic number of G, denoted by χzz(G), is the minimum number of colors needed for a total coloring of G. The Total Coloring Conjecture (TCC) proposed independently by Behzad and Vizing claims that, Δ(G) + 1 ≤ χ"(G) ≤ Δ(G) + 2, where Δ(G) is the maximum degree of G. The lower bound is sharp and the upper bound remains to be proved. In this paper, we prove the TCC for certain classes of lexicographic and deleted lexicographic products of graphs. Also, we obtained the lower bound for certain classes of these products. [ABSTRACT FROM AUTHOR]

Let tp (G) denote the number of paths in a graph G and let f: E → Z+ be an edge labeling of G. The weight of a path P is the sum of the labels assigned to the edges of P. If the set of weights of the paths in G is {1, 2, 3,..., tp (G)}, then f is called a Leech labeling of G and a graph which admits a Leech labeling is called a Leech graph. In this paper, we prove that the complete bipartite graphs K2, n and K3, n are not Leech graphs and determine the maximum possible value that can be given to an edge in the Leech labeling of a cycle. [ABSTRACT FROM AUTHOR]

Graphs are powerful tools to model manufacturing systems and scheduling problems. The complexity of these systems and their scheduling problems has been substantially increased by the ongoing technological development. Thus, it is essential to generate sustainable graph-based modeling approaches to deal with these excessive complexities. Graphs employ nodes and edges to represent the relationships between jobs, machines, operations, etc. Despite the significant volume of publications applying graphs to shop scheduling problems, the literature lacks a comprehensive survey study. We proposed the first comprehensive review paper which (1) systematically studies the overview and the perspective of this field, (2) highlights the gaps and potential hotspots of the literature, and (3) suggests future research directions towards sustainable graphs modeling the new intelligent/complex systems. We carefully examined 143 peer-reviewed journal papers published from 2015 to 2020. About 70% of our dataset were published in top-ranked journals which confirms the validity of our data and can imply the importance of this field. After discussing our generic data collection methodology, we proposed categorizations over the properties of the scheduling problems and their solutions. Then, we discussed our novel categorization over the variety of graphs modeling scheduling problems. Finally, as the most important contribution, we generated a creative graph-based model from scratch to represent the gaps and hotspots of the literature accompanied with statistical analysis on our dataset. Our analysis showed a significant attention towards job shop systems (56%) and Un/Directed Graphs (52%) where edges can be either directed, or undirected, or both, Whereas 14% of our dataset applied only Undirected Graphs and 11% targeted hybrid systems, e.g., mixed shop, flexible, and cellular manufacturing systems, which shows potential future research directions. [ABSTRACT FROM AUTHOR]

With the widespread use of UAVs, it is gradually difficult for single UAV to meet the needs of increasingly complex scenarios. At the same time, the problems of low autonomy and high dependence on control stations in central UAV cluster networks are gradually highlighted. In this paper, we analyze the theoretical conditions of network topology establishment and network connectivity, design a series of UAV distributed cluster automation control algorithm frameworks, and achieve certain research results, taking the distributed clusters of flight self-organizing networks as the background and using mathematical tools such as algebraic graph theory and random geometry to build a vibration sensor array model based on multiple intelligent sensor management. Based on this, a distributed connectivity maintenance algorithm based on the importance of nodes is designed to realize the "self-healing" of the flight's self-organizing network. This study also improves the Mavlink flight control communication protocol customization and Zigbee wireless networking mode design to solve the UAV swarm communication link collision problem. Compared with the existing distributed spectrum estimation-based node importance algorithm, the proposed algorithm further analyzes the topological changes caused by the removal of associated edges by failed nodes and the reconstruction of new associated edges between neighboring nodes, so that the theoretical results are closer to the actual topological dynamics of the flight self-organizing network. [ABSTRACT FROM AUTHOR]

In the current era of increasingly complex social life, as people's demand quality is getting higher and higher, the solution of the problem often has multiple indicators to achieve the optimum. This forces the graph coloring problem (GCP) to become complicated, and it is difficult to directly obtain the optimal solution, which brings new challenges to the solution of the problem. In response to this problem, the GCP field is of great research significance. With the in-depth study of GCP, the research on multiobjective optimization (MOO) in graph coloring algorithm (GCA) is gradually carried out. Its performance advantage is of great significance for solving multicondition constraint problems. This paper aims to study the application of Genetic Algorithm (GA) in GCA. Through the analysis and research of GA, and the fusion of numerical analysis and scientific computing, it can be applied to the construction of the neighbor distinguishable uniform V-full coloring algorithm (AVDEVTCA) to solve the AVDEVTC problem. This paper describes the basic theory of MOO and graph coloring. It conducts an experimental analysis of the algorithm performance and uses the relevant theoretical formulas to explain it. The results show that the algorithm takes 5754.142 S seconds to test 21325415 images and can color a large number of results that cannot be done manually in less time. It has greatly improved in terms of time and manpower saving and greatly improved practicability and work efficiency. [ABSTRACT FROM AUTHOR]

A block code is called a locally recoverable code (LRC for short) with $(r,\delta)$ -locality, if subject to any $\delta -1$ erasure failures, every symbol in the encoding can still be recovered by accessing at most $r$ other symbols. Recently, it was discovered by several authors that a $q$ -ary optimal $(r,\delta)$ -LRC, i.e., an LRC achieving the generalized Singleton-type bound, can have length much bigger than $q+1$. This is quite different from the classical $q$ -ary MDS codes where it is conjectured that the code length is upper bounded by $q+1$ (or $q+2$ for some special cases). In this paper, we further investigate constructions of optimal $(r,\delta)$ -LRCs along the line of using parity-check matrices. Inspired by classical Reed-Solomon codes and the work in Jin (2019), we equip parity-check matrices with the Vandermonde structure. It turns out that a parity-check matrix with the Vandermonde structure that produces an optimal LRC must obey certain disjoint property for subsets of $\mathbb {F}_{q}$. We manage to show the existence of these disjoint subsets. Thus, this yields an optimal $(r,\delta)$ -LRC with code length $\Omega \left({q^{\frac {\delta }{2}\left({1+\frac {1}{\lfloor \frac {d-1}{\delta }\rfloor -1}}\right)}}\right)\vphantom {\bigg)_{j}}$ , where $d$ is the minimum distance. In particular, to our surprise, for $\delta =2$ this disjoint condition is equivalent to a well-studied problem in extremal graph theory. With the help of extremal graph theory, we succeed to improve all of the best known results in Guruswami et al. (2018) for $d\geq 7$. In addition, for $d=6$ , we are able to remove the constraint required in Jin (2019) that $q$ is even. [ABSTRACT FROM AUTHOR]

Popular graph neural networks implement convolution operations on graphs based on polynomial spectral filters. In this paper, we propose a novel graph convolutional layer inspired by the auto-regressive moving average (ARMA) filter that, compared to polynomial ones, provides a more flexible frequency response, is more robust to noise, and better captures the global graph structure. We propose a graph neural network implementation of the ARMA filter with a recursive and distributed formulation, obtaining a convolutional layer that is efficient to train, localized in the node space, and can be transferred to new graphs at test time. We perform a spectral analysis to study the filtering effect of the proposed ARMA layer and report experiments on four downstream tasks: semi-supervised node classification, graph signal classification, graph classification, and graph regression. Results show that the proposed ARMA layer brings significant improvements over graph neural networks based on polynomial filters. [ABSTRACT FROM AUTHOR]

Weakly completely prime graph of a near ring (W1 (N)) was defined in this paper, the relationship between the elements of a near ring was determined by a definition of weakly completely prime ideal, so we studied many concepts related to the statements of the given near ring. We also found some theories related to previous graphs of our papers. [ABSTRACT FROM AUTHOR]

This paper investigates the periodic event-triggered asymmetric bipartite consensus problem of multi-agent systems (MASs) under structurally balanced undirected signed graphs. In order to reduce the consumption of communication resources and continuous detection in the control process of MASs, a novel periodic detection event-triggered asymmetric bipartite consensus control protocol is proposed. In particular, each agent samples only in a fixed period. For each agent, two event conditions are given, and only when state error satisfies this event condition can the event be triggered. A new type of Laplacian matrix is constructed to achieve asymmetric bipartite consensus. The control method can guarantee the performance of MASs and have less communication resources. Based on the Lyapunov stability theorem and algebraic graph theory, the proposed periodic event-triggered control strategy is able to implement the asymmetric bipartite consensus when the topology is structurally balanced undirected signed graphs. The proposed method in this paper can reduce the restriction on the sampling period and automatically exclude Zeno behavior. Finally, the validity of the conclusion is verified by numerical simulation. [ABSTRACT FROM AUTHOR]

Lots of symmetric properties are well-explored and analyzed in extremal graph theory, such as the well-known symmetrization operation in the Turán problem and the high symmetric in the extremal graphs. This paper is devoted to studying the Lagrangian of hypergraphs, which connects to a very symmetric function—the Lagrangian function. Given an r-uniform hypergraph F, the Lagrangian density π λ (F) is the limit supremum of r ! λ (G) over all F-free G, where λ (G) is the Lagrangian of G. An r-uniform hypergraph F is called λ -perfect if π λ (F) equals r ! λ (K v (F) − 1 r) . Yan and Peng conjectured that: for integer r ≥ 3 , there exists n 0 (r) such that if G and H are two λ -perfect r-graphs with | V (G) | and | V (H) | no less than n 0 (r) , then the disjoint union of G and H is λ -perfect. Let S t denote a 3-uniform hypergraph with t edges { e 1 , ⋯ , e t } satisfying that e i ∩ e j = { v } for all 1 ≤ i < j ≤ t . In this paper, we show that the conjecture holds for G = S 2 and H = S t for all t ≥ 62 . Moreover, our result yields a class of Turán densities of 3-uniform hypergraphs. In our proof, we use some new techniques to study Lagrangian density problems; using a result of Sidorenko to find subgraphs, and a result of Talbot to upper bound the Lagrangian of a hypergraph. [ABSTRACT FROM AUTHOR]

In this paper, a point-to-point network transmission control problem is formulated as a Markov decision process (MDP). Classical dynamic programming techniques such as value iteration, policy iteration, and linear programming can be employed to solve the optimization problem, but they suffer from high-computational complexity in networks with large state space. To achieve complexity reduction, the structure of the optimal policy can be exploited and incorporated into standard algorithms. In addition, function approximation can also be applied, where the value function is approximated by the linear combination of some basis vectors in a lower dimensional subspace. The main challenge for function approximation lies in the absence of general guidelines for subspace construction. In this paper, a proper subspace for projection is first generated based on system information, and more general construction methods are proposed using tools from graph signal processing (GSP). Graph symmetrization methods are also used to tackle the directed nature of the probability transition graph so that the well-developed GSP theory for undirected graphs can be employed. The numerical results for a typical wireless system show that standard algorithms with structural information incorporated can achieve 50% complexity reduction without performance loss. The subspace generated from the system can achieve zero policy error with faster runtime, and the GSP approach can also provide a proper subspace for perfect reconstruction of the optimal policy. It is also shown that how the proposed method can be applied to other MDP problems. [ABSTRACT FROM AUTHOR]