Search

A clique is a maximal complete subgraph of a graph. The cc-degree (clique-clique degree) of a clique K (dcc(K)) is the number of cliques adjacent to K. A clique C strongly clique-dominates a clique K if C is adjacent to K and dcc(C) ≥ dcc(K). Let C(G) be the set of all cliques in a graph G. A set S ⊆ C(G) is a strong clique-clique dominating set (SCCDset) of G if every clique in C(G)-S is strongly clique-dominated by at least one clique in S. The strong clique-clique domination number γscc(G) is the cardinality of a smallest SCCD-set of G. Similarly, the weak clique-clique domination number γwcc(G) is defined. In this paper, we study some properties of these strong (weak) clique-clique domination parameters and obtain Gallaitype results. We present an algorithm to find γscc(G) (γwcc(G)) and obtain some bounds for the newly defined parameters. Further, we define and study clique-clique domination balanced graphs and clique-posets. [ABSTRACT FROM AUTHOR]

An edge flipping is a non-reversible Markov chain on a given connected graph, as defined in Chung and Graham (2012). In the same paper, edge flipping eigenvalues and stationary distributions for some classes of graphs were identified. We further study edge flipping spectral properties to show a lower bound for the rate of convergence in the case of regular graphs. Moreover, we show by a coupling argument that a cutoff occurs at $\frac{1}{4} n \log n$ for the edge flipping on the complete graph. [ABSTRACT FROM AUTHOR]

For a graph G with n vertices, average distance µ(G) is the ratio of sum of the lengths of the shortest paths between all pairs of vertices to the number of edges in a complete graph on n vertices. In this paper, we introduce average distance colouring and find the average distance colouring number of certain classes of graphs. [ABSTRACT FROM AUTHOR]

In this paper, we introduce, study and analyze several classes of compact formulations for the symmetric Hamiltonian p$$ p $$‐median problem (Hp$$ p $$MP). Given a positive integer p$$ p $$ and a weighted complete undirected graph G=(V,E)$$ G=\left(V,E\right) $$ with weights on the edges, the Hp$$ p $$MP on G$$ G $$ is to find a minimum weight set of p$$ p $$ elementary cycles partitioning the vertices of G$$ G $$. The advantage of developing compact formulations is that they can be readily used in combination with off‐the‐shelf optimization software, unlike other types of formulations possibly involving the use of exponentially sized sets of variables or constraints. The main part of the paper focuses on compact formulations for eliminating solutions with less than p$$ p $$ cycles. Such formulations are less well known and studied than formulations which prevent solutions with more than p$$ p $$ cycles. The proposed formulations are based on a common motivation, that is, the formulations contain variables that assign labels to nodes, and prevent less than p$$ p $$ cycles by stating that different depots must have different labels and that nodes in the same cycle must have the same label. We introduce and study aggregated formulations (which consider integer variables that represent the label of the node) and disaggregated formulations (which consider binary variables that assign each node to a given label). The aggregated models are new. The disaggregated formulations are not, although in all of them new enhancements have been included to make them more competitive with the aggregated models. The two main conclusions of this study are: (i) in the context of compact formulations, it is worth looking at the models with integer node variables, which have a smaller size. Despite their weaker LP relaxation bounds, the fewer variables and constraints lead to faster integer resolution, especially when solving instances with more than 50 nodes; (ii) the best of our compact models exhibit a performance that, overall, is comparable to that of the best methods known for the Hp$$ p $$MP (including branch‐and‐cut algorithms), solving to optimality instances with up to 226 nodes within 1 h. This corroborates our message that the knowledge of the inequalities for preventing less than p$$ p $$ cycles is much less well understood. [ABSTRACT FROM AUTHOR]

With the rapid development of smart technologies, the Internet of Vehicles (IoV) is revolutionizing transportation and mobility. However, the complexity and interconnectedness of IoV systems lead to a growing number of security incidents caused by vulnerabilities. Current vulnerability classification algorithms often struggle to address the low occurrence frequency and incomplete information associated with IoV vulnerabilities, resulting in decreased precision and recall rates of classifiers. To address these challenges, an effective vulnerability classification algorithm (KG-KNN), is proposed, designed to handle imbalanced sample data. KG-KNN integrates the vulnerability information of IoV and the association relationship between features by constructing a feature knowledge graph to form a complete knowledge system. It adds the correlation relationship between features to the similarity calculation, calculates vulnerability similarity from multiple dimensions, and improves the prediction performance of the classifier. The experimental results show that compared to the k-NearestNeighbor (KNN), Support Vector Machine (SVM), Deep Nueral Network (DNN) and TFI-DNN classification algorithms, KG-KNN can effectively deal with imbalanced sample data and has different degrees of improvement in precision, recall, and the F1 score. [ABSTRACT FROM AUTHOR]

Text classification is the task of estimating the genre of a document based on information such as word co-occurrence and frequency of occurrence. Text classification has been studied by various approaches. In this study, we focused on text classification using graph structure data. Conventional graph-based methods express relationships between words and relationships between words and documents as weights between nodes. Then, a graph neural network is used for learning. However, there is a problem that conventional methods are not able to represent the relationship between documents on the graph. In this paper, we propose a graph structure that considers the relationships between documents. In the proposed method, the cosine similarity of document vectors is set as weights between document nodes. This completes a graph that considers the relationship between documents. The graph is then input into a graph convolutional neural network for training. Therefore, the aim of this study is to improve the text classification performance of conventional methods by using this graph that considers the relationships between document nodes. In this study, we conducted evaluation experiments using five different corpora of English documents. The results showed that the proposed method outperformed the performance of the conventional method by up to 1.19%, indicating that the use of relationships between documents is effective. In addition, the proposed method was shown to be particularly effective in classifying long documents. [ABSTRACT FROM AUTHOR]

It is shown that a locally finite ultrametric space (X, d) is generated by a labeled tree if and only if for every open ball B ⊆ X there is a point c ∈ B such that d(x, c) = diam B whenever x ∈ B and x ≠ c. For every finite ultrametric space Y, we construct an ultrametric space Z having the smallest possible number of points such that Z is generated by a labeled tree and Y is isometric to a subspace of Z. It is proved that for a given Y such a space Z is unique up to isometry. [ABSTRACT FROM AUTHOR]

Deep neural network models (DNNs) are essential to modern AI and provide powerful models of information processing in biological neural networks. Researchers in both neuroscience and engineering are pursuing a better understanding of the internal representations and operations that undergird the successes and failures of DNNs. Neuroscientists additionally evaluate DNNs as models of brain computation by comparing their internal representations to those found in brains. It is therefore essential to have a method to easily and exhaustively extract and characterize the results of the internal operations of any DNN. Many models are implemented in PyTorch, the leading framework for building DNN models. Here we introduce TorchLens, a new open-source Python package for extracting and characterizing hidden-layer activations in PyTorch models. Uniquely among existing approaches to this problem, TorchLens has the following features: (1) it exhaustively extracts the results of all intermediate operations, not just those associated with PyTorch module objects, yielding a full record of every step in the model's computational graph, (2) it provides an intuitive visualization of the model's complete computational graph along with metadata about each computational step in a model's forward pass for further analysis, (3) it contains a built-in validation procedure to algorithmically verify the accuracy of all saved hidden-layer activations, and (4) the approach it uses can be automatically applied to any PyTorch model with no modifications, including models with conditional (if–then) logic in their forward pass, recurrent models, branching models where layer outputs are fed into multiple subsequent layers in parallel, and models with internally generated tensors (e.g., injections of noise). Furthermore, using TorchLens requires minimal additional code, making it easy to incorporate into existing pipelines for model development and analysis, and useful as a pedagogical aid when teaching deep learning concepts. We hope this contribution will help researchers in AI and neuroscience understand the internal representations of DNNs. [ABSTRACT FROM AUTHOR]

Relational learning has attracted much attention from the machine learning community in recent years, and many real-world applications have been successfully formulated as relational learning problems. In recent years, several relational learning algorithms have been introduced that follow a pattern-based approach. However, this type of learning model suffers from two fundamental problems: the computational complexity arising from relational queries and the lack of a robust and general framework to serve as the basis for relational learning methods. In this paper, we propose an efficient graph query framework that allows for cyclic queries in polynomial time and is ready to be used in pattern-based learning methods. This solution uses logical predicates instead of graph isomorphisms for query evaluation, reducing complexity and allowing for query refinement through atomic operations. The main differences between our method and other previous pattern-based graph query approaches are the ability to evaluate arbitrary subgraphs instead of nodes or complete graphs, the fact that it is based on mathematical formalization that allows the study of refinements and their complementarity, and the ability to detect cyclic patterns in polynomial time. Application examples show that the proposed framework allows learning relational classifiers to be efficient in generating data with high expressiveness capacities. Specifically, relational decision trees are learned from sets of tagged subnetworks that provide both classifiers and characteristic patterns for the identified classes. [ABSTRACT FROM AUTHOR]

For a positive integer n , we use K n and P n to denote a complete graph and an induced path on n vertices, respectively. A subdivision of G is a graph obtained from G by replacing the edges of G with independent paths of length at least one between their end vertices. A graph is said to be ISK 4 - free if it does not contain any subdivision of K 4 as an induced subgraph. Lévêque, Maffray and Trotignon conjectured that every ISK 4 -free graph is 4-colorable. In this paper, we show that this conjecture is true for the class of P 6 -free graphs. [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]

Background: Evolutionary scenarios describing the evolution of a family of genes within a collection of species comprise the mapping of the vertices of a gene tree T to vertices and edges of a species tree S. The relative timing of the last common ancestors of two extant genes (leaves of T) and the last common ancestors of the two species (leaves of S) in which they reside is indicative of horizontal gene transfers (HGT) and ancient duplications. Orthologous gene pairs, on the other hand, require that their last common ancestors coincides with a corresponding speciation event. The relative timing information of gene and species divergences is captured by three colored graphs that have the extant genes as vertices and the species in which the genes are found as vertex colors: the equal-divergence-time (EDT) graph, the later-divergence-time (LDT) graph and the prior-divergence-time (PDT) graph, which together form an edge partition of the complete graph. Results: Here we give a complete characterization in terms of informative and forbidden triples that can be read off the three graphs and provide a polynomial time algorithm for constructing an evolutionary scenario that explains the graphs, provided such a scenario exists. While both LDT and PDT graphs are cographs, this is not true for the EDT graph in general. We show that every EDT graph is perfect. While the information about LDT and PDT graphs is necessary to recognize EDT graphs in polynomial-time for general scenarios, this extra information can be dropped in the HGT-free case. However, recognition of EDT graphs without knowledge of putative LDT and PDT graphs is NP-complete for general scenarios. In contrast, PDT graphs can be recognized in polynomial-time. We finally connect the EDT graph to the alternative definitions of orthology that have been proposed for scenarios with horizontal gene transfer. With one exception, the corresponding graphs are shown to be colored cographs. [ABSTRACT FROM AUTHOR]

Spectral graph theory is like a special tool for understanding graphs. It helps us find patterns and connections in complex networks, using the magic of eigenvalues. Let G be the graph and A (G) be its adjacency matrix, then G is singular if the determinant of the adjacency matrix A (G) is 0, otherwise it is nonsingular. Within the realm of nonsingular graphs, there is the concept of property R , where each eigenvalue's reciprocal is also an eigenvalue of G. By introducing multiplicity constraints on both eigenvalues and their reciprocals, it becomes property SR. Similarly, the world of nonsingular graphs reveals property − R , where the negative reciprocal of each eigenvalue also finds a place within the spectrum of G. Moreover, when the multiplicity of each eigenvalue and its negative reciprocal is equal, this results in a graph with a property of − SR . Some classes of unweighted nonbipartite graphs are already constructed in the literature with the help of the complete graph K n and a copy of the path graph P 4 satisfying property R but not SR. This article takes this a step further. The main aim is to construct several weighted classes of graphs which satisfy property R but not SR. For this purpose, the weight functions are determined that enable these nonbipartite graph classes to satisfy the − SR and R properties, even if the unweighted graph does not satisfy these properties. Some examples are presented to support the investigated results. These examples explain how certain weight functions make these special types of graphs meet the properties R or − SR , even when the original graphs without weights do not meet these properties. [ABSTRACT FROM AUTHOR]

This paper studies a general class of stochastic population processes in which agents interact with one another over a network. Agents update their behaviors in a random and decentralized manner according to a policy that depends only on the agent's current state and an estimate of the macroscopic population state, given by a weighted average of the neighboring states. When the number of agents is large and the network is a complete graph (has all-to-all information access), the macroscopic behavior of the population can be well-approximated by a set of deterministic differential equations called a mean-field approximation. For incomplete networks such characterizations remained previously unclear, i.e., in general whether a suitable mean-field approximation exists for the macroscopic behavior of the population. The paper addresses this gap by establishing a generic theory describing when various mean-field approximations are accurate for arbitrary interaction structures. Our results are threefold. Letting W be the matrix describing agent interactions, we first show that a simple mean-field approximation that incorrectly assumes a homogeneous interaction structure is accurate provided W has a large spectral gap. Second, we show that a more complex mean-field approximation which takes into account agent interactions is accurate as long as the Frobenius norm of W is small. Finally, we compare the predictions of the two mean-field approximations through simulations, highlighting cases where using mean-field approximations that assume a homogeneous interaction structure can lead to inaccurate qualitative and quantitative predictions. [ABSTRACT FROM AUTHOR]

When a grounding fault occurs in the distribution network with distributed generation, the network topology becomes intricate, making it challenging to extract fault characteristics, resulting in a decrease in the precision of fault discrimination. To address this issue, a graph isomorphism network (GIN) approach based on the parameterized adaptive graph learning (AdapGL) module is proposed, transforming the distribution network fault selection problem into a graph classification task. First, the adjacency matrix of the distribution network's topology graph is initialized. This matrix, combined with feature vectors from the robust local mean decomposition energy entropy and transient dielectric loss angle of line, will be input into the GIN. Then, the AdapGL module is integrated into the GIN, dynamically learning and updating the one‐way relationships between actual network nodes to complete the graph classification task. Finally, a radial distribution network model (RDNM) and an improved IEEE 34 nodes model are established, and the fault selection results of the AdapGL‐GIN method are compared with those of other methods. The results indicate that the proposed method achieves higher accuracy than other methods, demonstrating significant practical importance in engineering applications. [ABSTRACT FROM AUTHOR]

In recent years, the development of graph states has opened a bright prospect for the generation of multipartite entangled states. However, due to the influences of noises in the surroundings, the obtained graph states may not be maximally entangled, which have been rarely explored previously. In this paper, we first consider how to generate one particular graph state which is named as the non-maximally entangled graph state. Next, we analyze the properties of the non-maximally entangled graph states and introduce two different kinds of graph states according to the entanglement of the non-maximally entangled graph states. Finally, we demonstrate how to teleport arbitrary unknown single-qubit state by using the non-maximally graph states. Compared with previous teleportation protocol, it demonstrates higher efficiency and lower operational complexity. We expect that our works can provide a theoretical instruction for the future study of the graph states. [ABSTRACT FROM AUTHOR]

The crossing number cr(G) of a graph G is the minimum number of edge crossings over all drawings of G in the plane. In the paper, we extend known results concerning crossing numbers of join products of four small graphs with paths and cycles. The crossing numbers of the join products G∗ + Pn and G∗ + Cn for the disconnected graph G∗ consisting of the complete tripartite graph K1,1,2 and one isolated vertex are given, where Pn and Cn are the path and the cycle on n vertices, respectively. In the paper also the crossing numbers of H∗ + Pn and H∗ + Cn are determined, where H∗ is isomorphic to the complete tripartite graph K1,1,3. Finally, by adding new edges to the graphs G∗ and H∗, we are able to obtain crossing numbers of join products of two other graphs G1 and H1 with paths and cycles. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a simple graph of order p and size q. A graph G is called local antimagic (total) if G admits a local antimagic (total) labeling. A bijection g : E → {1, 2, . . ., q} is called a local antimagic labeling of G if for any two adjacent vertices u and v, we have g+(u) ̸= g+(v), where g+(u) = Σe∈E(u) g(e), and E(u) is the set of edges incident to u. Similarly, a bijection f : V (G)∪E(G) → {1, 2, . . ., p+q} is called a local antimagic total labeling of G if for any two adjacent vertices u and v, we have wf (u) ̸= wf (v), where wf (u) = f(u) + Σe∈E(u)f(e). Thus, any local antimagic (total) labeling induces a proper vertex coloring of G if vertex v is assigned the color g+(v) (respectively, wf (u)). The local antimagic (total) chromatic number, denoted χla(G) (respectively χlat(G)), is the minimum number of induced colors taken over local antimagic (total) labeling of G. We provide a short proof that every graph G is local antimagic total. The proof provides sharp upper bound to χlat(G). We then determined the exact χlat(G), where G is a complete bipartite graph, a path, or the Cartesian product of two cycles. Consequently, the χla(G ∨ K1) is also obtained. Moreover, we determined the χla(G ∨ K1) and hence the χlat(G) for a class of 2-regular graphs G (possibly with a path). The work of this paper also provides many open problems on χlat(G). We also conjecture that each graph G of order at least 3 has χlat(G) ≤ χla(G). [ABSTRACT FROM AUTHOR]

We examine the necessary and sufficient conditions for a complete symmetric equipartite digraph Kn[m]* ${K}_{n[m]}^{* }$ with n $n$ parts of size m $m$ to admit a resolvable decomposition into directed cycles of length t $t$. We show that the obvious necessary conditions are sufficient for m,n,t≥2 $m,n,t\ge 2$ in each of the following four cases: (i) m(n−1) $m(n-1)$ is even; (ii) gcd(m,n)∉{1,3} $\text{gcd}(m,n)\notin \{1,3\}$; (iii) gcd(m,n)=1 $\text{gcd}(m,n)=1$ and 4∣n $4| n$ or 6∣n $6| n$; and (iv) gcd(m,n)=3 $\text{gcd}(m,n)=3$, and if n=6 $n=6$, then p∣m $p| m$ for a prime p≤37 $p\le 37$. [ABSTRACT FROM AUTHOR]

Cameron defined the concept of generalized t $t$‐designs, which generalized t $t$‐designs, resolvable designs and orthogonal arrays. This paper introduces a new class of combinatorial designs which simultaneously provide a generalization of both generalized t $t$‐designs and group divisible t $t$‐designs. In certain cases, we derive necessary conditions for the existence of generalized group divisible t $t$‐designs, and then point out close connections with various well‐known classes of designs, including mixed orthogonal arrays, factorizations of the complete multipartite graphs, large sets of group divisible designs, and group divisible designs with (orthogonal) resolvability. Moreover, we investigate constructions for generalized group divisible t $t$‐designs and almost completely determine their existence for t=2,3 $t=2,3$ and small block sizes. [ABSTRACT FROM AUTHOR]

The prime graph Δ ⁢ (G) of a finite group 퐺 is a graph whose vertex set is the set of prime factors of the degrees of all irreducible complex characters of 퐺, and two distinct primes 푝 and 푞 are joined by an edge if the product p ⁢ q divides some character degree of 퐺. In 2014, Tong-Viet [H. P. Tong-Viet, Finite groups whose prime graphs are regular, J. Algebra397 (2014), 18–31] proposed the following conjecture. Let 퐺 be a group and let k ≥ 5 be odd. If the prime graph Δ ⁢ (G) is 푘-regular, then Δ ⁢ (G) is a complete graph of order k + 1 . In this paper, we show that if the prime graph Δ ⁢ (G) of a finite nonsolvable group 퐺 is 5-regular, then Δ ⁢ (G) is isomorphic to the complete graph K 6 or possibly the graph depicted in the first figure below. Moreover, if 퐺 is an almost simple group, then Δ ⁢ (G) is isomorphic to the complete graph K 6 . [ABSTRACT FROM AUTHOR]

A pseudo coloring of the vertices of a graph G, is a coloring assigned to the vertices of G such that adjacent vertices can receive the same colors. A pseudo complete coloring of a graph G is a pseudo coloring of the vertices of G, such that for any pair of distinct colors, there is at least one edge whose end vertices are colored with this pair of colors. The maximum number of colors used in a pseudo complete coloring of G is called the pseudo achromatic number, denoted by ψs(G). A neighborhood pseudo chromatic number of a graph G, denoted by ψnhd(G), is the maximum number of colors used in a pseudo coloring of G, such that every vertex has at least two vertices in its closed neighborhood receiving the same color. Here, we defined a new coloring parameter called neighborhood pseudo achromatic number of a graph G and obtained neighborhood pseudo achromatic number of a complete p-partite graph by analysing various possibilitie [ABSTRACT FROM AUTHOR]

In this paper, we investigate the notion of quadratic exponential invertible graphs whose vertex set is reduced residue system mod n and there will be an edge between x and y such that x2α ≡ y2α (mod n) for some positive integer α. The proposed graph is completely characterized for each positive integer n and also, we find the class of integers in which quadratic exponential invertible graphs are isomorphic to each other. Moreover, the class of those integers is investigated in which the proposed graph is a complete graph. [ABSTRACT FROM AUTHOR]

Let G be a subgraph of the complete bipartite graph K l , m , l ≤ m , with e = q m + p > 0 , 0 ≤ p < m , edges. The maximal value of the sum of the squares of the degrees of the vertices of G is q m 2 + p 2 + p (q + 1) 2 + (m - p) q 2 . We classify all graphs that attain this bound using the diagonal sequence of a partition. [ABSTRACT FROM AUTHOR]

In this paper, we prove that the set of all paths of a fixed length in a complete multipartite graph is the bases of a matroid. Moreover, we discuss the Cohen–Macaulayness and depth of powers of t -path ideals of a complete multipartite graph. [ABSTRACT FROM AUTHOR]

The graph obtained by joining cycle C m to a path P n with a bridge is called Tadpole graph denoted by T m , n . A subset D of V (G) is said to be a tadpole dominating set of G if D is a dominating set and the set of vertices of D spans a tadpole graph T m , n where m ≥ 3 , n ≥ 1. In this paper, we find the tadpole domination number of cartesian product of certain graphs, namely, paths, cycles and complete graphs. Also the tadpole domination number for the Mycielskian of cycles and paths is obtained. [ABSTRACT FROM AUTHOR]

Let G be a graph. A vertex-cut S of G is said to be k-restricted if every component of G − S has at least k vertices, and cyclic if G − S has at least two components which contain a cycle. The minimum cardinality over all k -restricted vertex-cuts of G is called the k-restricted connectivity of G and is denoted by κ k (G). Also the minimum cardinality over all cyclic vertex-cuts of G is called the cyclic connectivity of graph G and is denoted by κ c (G). In this paper, the k -restricted connectivity and cyclic connectivity of the direct product of two graphs G 1 and G 2 is obtained for some k ≥ 2 , where G 1 is a complete graph, and G 2 is a complete graph, a complete bipartite graph or a cycle. [ABSTRACT FROM AUTHOR]

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

A graph is called $k$ -critical if its chromatic number is $k$ but every proper subgraph has chromatic number less than $k$. An old and important problem in graph theory asks to determine the maximum number of edges in an $n$ -vertex $k$ -critical graph. This is widely open for every integer $k\geq 4$. Using a structural characterisation of Greenwell and Lovász and an extremal result of Simonovits, Stiebitz proved in 1987 that for $k\geq 4$ and sufficiently large $n$ , this maximum number is less than the number of edges in the $n$ -vertex balanced complete $(k-2)$ -partite graph. In this paper, we obtain the first improvement in the above result in the past 35 years. Our proofs combine arguments from extremal graph theory as well as some structural analysis. A key lemma we use indicates a partial structure in dense $k$ -critical graphs, which may be of independent interest. [ABSTRACT FROM AUTHOR]

In this paper, we introduce and study the annihilating-ideal graph of an MV-algebra (A, ⊕, ∗, 0). The algebraic structure of MV-algebras (especially Boolean algebras) are described by using the annihilating-ideal graph. The connections between the ideal theory of MV-algebras and graph theory are established, which promote the studying of the coloring of graphs. The annihilating-ideal graph AG(A) is a simple graph with the vertex set V (AG(A)) = {I ∈ I(A)\{h0i, A} | ∃J ∈ I ∗ (A) such that IJ = h0i} and the edge set E(AG(A)) = {I − J | IJ = h0i, where I, J ∈ V (AG(A)) and I 6= J}, where I(A) is the set of all ideals of A and I ∗ (A) = I(A)\{h0i}. We verify that AG(A) is connected with dmax(AG(A)) ≤ 3. And we characterize some MV-algebras with dmax(AG(A)) = 0 or 1, where dmax(AG(A)) is the diameter of AG(A). If | A |≤ 7, we show that AG(A) is either a null graph, or dmax(AG(A)) = 1. We restrict MV-algebras to Boolean algebras. The connections between AG(A) and Γ(A) are studied, where Γ(A) is the zero-divisor graph of A. We characterize the complete graph AG(A) and the star graph AG(A) by using ann(A\{1}) = {a ∈ A | a ⊙ b = 0 for all b ∈ A\{1}}, where ann(A\{1}) is the annihilator of A\{1}. Finally, we study the vertex coloring and girth of AG(A). We give two lower bounds and an upper bound for χ(AG(A)). [ABSTRACT FROM AUTHOR]

One of the 148 discrete Adria indices is the symmetric division deg (SDD) index. It was developed about 13 years ago. Motivated by the success of the symmetric division deg index, Ghorbani et al. recently proposed an inverse version of this index, which they called the ISDD index (Inverse symmetric division deg index). The inverse symmetric division deg index (ISDD) of a graph Γ is defined as follows: ISDD(Γ) = ∑vivj∈E(Γ) didj/di2 + dj2, ISDD (Γ) = ∑ v i v j ∈ E (Γ)   d i d j d i 2 + d j 2 , $$ \mathrm{ISDD}(\mathrm{\Gamma })=\sum_{{v}_i{v}_j\in E(\mathrm{\Gamma })} \enspace \frac{{d}_i{d}_j}{{d}_i^2+{d}_j^2}, $$ where di is the degree of the vertex vi in Γ. In this paper, we determine the second maximal and the second minimal trees with respect to the inverse symmetric division deg index (ISDD). We prove that the star gives the minimal and the complete bipartite graph K⌈n/2⌉, ⌊n/2⌋ K ⌈ n 2 ⌉ ,   ⌊ n 2 ⌋ $ {K}_{\lceil \frac{n}{2}\rceil,\enspace \lfloor \frac{n}{2}\rfloor }$ gives the maximal graphs with respect to the inverse symmetric division deg index (ISDD) among any chain graph of order n. Moreover, the Turán graph gives the maximal graph with respect to the ISDD index for any simple graph of order n with chromatic number k. Finally, we give concluding remarks about future works. [ABSTRACT FROM AUTHOR]

The eccentricity matrix of a graph is defined as the matrix obtained from its distance matrix by retaining the largest elements in each row and column, while the rest elements are set to be zero. The eccentricity eigenvalues of a graph are the eigenvalues of its eccentricity matrix, the eccentricity energy of a graph is the sum of the absolute values of its eccentricity eigenvalues, and the eccentricity spectral radius of a graph is its largest eccentricity eigenvalue. Let gn,d G n , d $ {\mathcal{G}}_{n,d}$ be the set of n-vertex connected graphs with odd diameter d, where each graph G in gn,d G n , d $ {\mathcal{G}}_{n,d}$ has a diametrical path whose center edge is a cut edge of G. For any graph G in gn,d G n , d $ {\mathcal{G}}_{n,d}$ , we construct a weighted graph Hω such that its adjacency matrix is just the eccentricity matrix of G, where H is the sequential join graph of the complement graphs of four disjoint complete graphs. In terms of the energy and spectral radius of the weighted graphs, we determine the graphs with minimum eccentricity energy, minimum and maximum eccentricity spectral radius in gn,d G n , d $ {\mathcal{G}}_{n,d}$ , respectively. As corollaries, we determine the trees with minimum eccentricity energy, minimum and maximum eccentricity spectral radius among all trees with odd diameter, respectively. [ABSTRACT FROM AUTHOR]

We consider potential-based flow networks with terminal nodes at which flow can enter or leave the network and physical properties, such as voltages or pressures, are measured and controlled. We study conditions under which such a network can be reduced to a smaller, equivalent network with the same behavior at the terminal nodes. Potential-based flow networks are widely used to model infrastructure networks, such as electricity, gas, or water networks. In contrast to Kron's reduction for electrical networks, we prove that, in general, potential-based flow networks with at least three terminals cannot be reduced to smaller networks whose size only depends on the number of terminals. On the other hand, we show that it is possible to represent a special class of potential-based flow networks by a complete graph on the terminals, and we establish a characterization of networks that can be reduced to a path network. Our results build on fundamental properties of effective resistances proved in this paper, including explicit formulae for their dependence on edge resistances of the network and their metric properties. Funding: This work was supported by Deutsche Forschungsgemeinschaft [Grants CRC/TRR 154, 239904186, Subproject A07]. [ABSTRACT FROM AUTHOR]

Logit dynamics is a form of randomized game dynamics in which players have a bias toward strategic deviations that give a higher improvement in cost. It is used extensively in practice. In congestion (or potential) games, the dynamics converge to the so-called Gibbs distribution over the set of all strategy profiles when interpreted as a Markov chain. In general, logit dynamics can converge slowly to the Gibbs distribution, but beyond that, not much is known about its algorithmic aspects, nor that of the Gibbs distribution. In this work, we are interested in the following two questions for congestion games: (i) Is there an efficient algorithm for sampling from the Gibbs distribution? (ii) If yes, does there also exist natural randomized dynamics that converge quickly to the Gibbs distribution? We first study these questions in extension parallel congestion games, a well-studied special case of symmetric network congestion games. As our main result, we show that there is a simple variation on the logit dynamics that converges quickly to the Gibbs distribution in such games. We also address the first question for the class of so-called capacitated uniform congestion games and the second question for max cut games played on a complete graph. To prove our results, we rely on the recent breakthrough work of Anari et al. (2019) regarding the approximate sampling of a base of a matroid according to a strongly log-concave probability distribution. [ABSTRACT FROM AUTHOR]

Recently, Behr (2020) introduced a notion of the chromatic index of signed graphs and proved that for every signed graph (G , σ) it holds that Δ (G) ≤ χ ′ (G , σ) ≤ Δ (G) + 1 , where Δ (G) is the maximum degree of G and χ ′ denotes its chromatic index. In general, the chromatic index of (G , σ) depends on both the underlying graph G and the signature σ. In the paper we study graphs G for which χ ′ (G , σ) does not depend on σ. To this aim we introduce two new classes of graphs, namely 1 ± and 2 ± , such that graph G is of class 1 ± (respectively, 2 ±) if and only if χ ′ (G , σ) = Δ (G) (respectively, χ ′ (G , σ) = Δ (G) + 1) for all possible signatures σ. We prove that all wheels, necklaces, complete bipartite graphs K r , t with r ≠ t and almost all cacti graphs are of class 1 ±. Moreover, we give sufficient and necessary conditions for a graph to be of class 2 ± , i.e. we show that these graphs must have odd maximum degree and give examples of such graphs with arbitrary odd maximum degree bigger than 1. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) , a subset S ⊆ V is 2- dominating if every vertex in S ¯ has at least two neighbors in S. The minimum cardinality of such a set is called the 2- domination number of G. Consider a process in discrete time that, starting with an initial set of marked vertices S , at each step marks all unmarked vertices having two marked neighbors. In such a process, the minimum number of initial vertices in S such that eventually all vertices are marked is called the P 3 - hull number of G. In this work, we explore a polyhedral relation between these two parameters and, in addition, we provide new families of valid inequalities for the associated polytopes. Finally, we give explicit descriptions of the polytopes associated to these problems when G is a path, a cycle, a complete graph, or a tree. [ABSTRACT FROM AUTHOR]

A series-parallel graph is a graph that does not contain a complete graph with four vertices as a minor. An explicit formula for the number of labeled series-parallel tricyclic graphs with a given number of vertices is obtained, and the corresponding asymptotics for the number of such graphs with a large number of vertices is found. We prove that under a uniform probability distribution, the probability that the labeled tricyclic graph is a series-parallel graph is asymptotically equal to 13/15. [ABSTRACT FROM AUTHOR]

A signed graph is a pair (G , Σ) , where G = (V , E) is a graph (in which parallel edges are permitted, but loops are not) with V = { 1 , ... , n } and Σ ⊆ E. The edges in Σ are called odd and the other edges of E even. If there are parallel edges, then only two edges in each parallel class are permitted, one of which is even and one of which is odd. By S (G , Σ) we denote the set of all symmetric n × n matrices A = [ a i , j ] with a i , j < 0 if i and j are connected by an even edge, a i , j > 0 if i and j are connected by an odd edge, a i , j ∈ R if i and j are connected by both an even and an odd edge, a i , j = 0 if i ≠ j and i and j are non-adjacent, and a i , i ∈ R for all vertices i. The maximum nullity M (G , Σ) of a signed graph (G , Σ) is the maximum nullity attained by any A ∈ S (G , Σ). Arav et al. gave a combinatorial characterization of 2-connected signed graphs (G , Σ) with M (G , Σ) = 2. In this paper, we give a complete combinatorial characterization of the signed graphs (G , Σ) with M (G , Σ) = 2. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a finite undirected graph. A set S of vertices in V is said to be total k -dominating if every vertex in V is adjacent to at least k vertices in S. The total k -domination number, γ k t (G) , is the minimum cardinality of a total k -dominating set in G. In this work we study the total k -domination number of Cartesian product of two complete graphs which is a lower bound of the total k -domination number of Cartesian product of two graphs. We obtain new lower and upper bounds for the total k -domination number of Cartesian product of two complete graphs. Some asymptotic behaviors are obtained as a consequence of the bounds we found. In particular, lim inf n → ∞ γ k t (G □ H) n : G , H are graphs of order n ≤ 2 k 2 − 1 + k + 4 2 − 1 − 1 . We also prove that the equality is attained if k is even. The equality holds when G , H are both isomorphic to the complete graph, K n , with n vertices. Furthermore, we obtain closed formulas for the total 2-domination number of Cartesian product of two complete graphs of whatever order. Besides, we prove that, for k = 3 , the inequality above is improvable to lim inf n → ∞ γ 3 t (K n □ K n) / n ≤ 11 / 5. [ABSTRACT FROM AUTHOR]

In this work we show that if iterates of a nonexpansive self-mapping of a complete metric with a graph converge uniformly on a subset of the space, then this convergence is stable under the presence of small computational errors. [ABSTRACT FROM AUTHOR]

The niche graph of a digraph D has V (D) as the vertex set and an edge uv if and only if (u,w) ∈ A(D) and (v,w) ∈ A(D), or (w, u) ∈ A(D) and (w, v) ∈ A(D) for some w ∈ V (D). The notion of niche graphs was introduced by Cable et al. [Niche graphs, Discrete Appl. Math. 23 (1989), 231-241] as a variant of competition graphs. If a graph is the niche graph of a digraph D, it is said to be niche-realizable through D. If a graph G is niche-realizable through a k-partite tournament for an integer k ≥ 2, then we say that the pair (G, k) is niche-realizable. Bowser et al. [Niche graphs and mixed pair graphs of tournaments, J. Graph Theory 31 (1999) 319-332] studied the graphs that are niche-realizable through a tournament and Eoh et al. [The niche graphs of bipartite tournaments, Discrete Appl. Math. 282 (2020) 86-95] recently studied niche-realizable pairs (G, k) for k = 2. In this paper, we extend their work for k ≥ 3. We show that the niche graph of a k-partite tournament has at most three components if k ≥ 3 and is connected if k ≥ 4. Then we find all the niche-realizable pairs (G, k) in each case: G is disconnected; G is a complete graph; G is connected and triangle-free. [ABSTRACT FROM AUTHOR]

Graph matching aims at finding the vertex correspondence between two unlabeled graphs that maximizes the total edge weight correlation. This amounts to solving a computationally intractable quadratic assignment problem. In this paper, we propose a new spectral method, graph matching by pairwise eigen-alignments (GRAMPA). Departing from prior spectral approaches that only compare top eigenvectors, or eigenvectors of the same order, GRAMPA first constructs a similarity matrix as a weighted sum of outer products between all pairs of eigenvectors of the two graphs, with weights given by a Cauchy kernel applied to the separation of the corresponding eigenvalues, then outputs a matching by a simple rounding procedure. The similarity matrix can also be interpreted as the solution to a regularized quadratic programming relaxation of the quadratic assignment problem. For the Gaussian Wigner model in which two complete graphs on n vertices have Gaussian edge weights with correlation coefficient 1 - σ 2 , we show that GRAMPA exactly recovers the correct vertex correspondence with high probability when σ = O (1 log n) . This matches the state of the art of polynomial-time algorithms and significantly improves over existing spectral methods which require σ to be polynomially small in n. The superiority of GRAMPA is also demonstrated on a variety of synthetic and real datasets, in terms of both statistical accuracy and computational efficiency. Universality results, including similar guarantees for dense and sparse Erdős–Rényi graphs, are deferred to a companion paper. [ABSTRACT FROM AUTHOR]

Completely independent spanning trees in a graph G are spanning trees of G such that for any two distinct vertices of G, the paths between them in the spanning trees are pairwise edge-disjoint and internally vertex-disjoint. In this paper, we present a tight lower bound on the maximum number of completely independent spanning trees in L(G), where L(G) denotes the line graph of a graph G. Based on a new characterization of a graph with k completely independent spanning trees, we also show that for any complete graph K n of order n ≥ 4 , there are ⌊ n + 1 2 ⌋ completely independent spanning trees in L (K n) where the number ⌊ n + 1 2 ⌋ is optimal, such that ⌊ n + 1 2 ⌋ completely independent spanning trees still exist in the graph obtained from L (K n) by deleting any vertex (respectively, any induced path of order at most n 2 ) for n = 4 or odd n ≥ 5 (respectively, even n ≥ 6 ). Concerning the connectivity and the number of completely independent spanning trees, we moreover show the following, where δ (G) denotes the minimum degree of G. Every 2k-connected line graph L(G) has k completely independent spanning trees if G is not super edge-connected or δ (G) ≥ 2 k . Every (4 k - 2) -connected line graph L(G) has k completely independent spanning trees if G is regular. Every (k 2 + 2 k - 1) -connected line graph L(G) with δ (G) ≥ k + 1 has k completely independent spanning trees. [ABSTRACT FROM AUTHOR]

A dominating set D of a graph G is said to be a k-isolate perfect dominating set(kIPDS) of G if has exactly k isolated vertices and D is a perfect dominating set of G. In this paper. we investigate the basic properties of kIPDS and provide the kIPD number of cycles. paths. complete a-partite graphs and some special graphs. [ABSTRACT FROM AUTHOR]

In the process of the battle between the enemy and us on the battlefield, accurately predicting the deployment of the enemy forces will be beneficial to our combat. Based on the situation data of wargame, this paper proposes a method for predicting the unknown operator position of the enemy by training Graph Neural Networks. Firstly, after preprocessing the data, the transformation from situation to graph structure data was realized， and the graph structure data set of wargame situation was constructed for training Graph Neural Networks. Secondly, according to the characteristics of wargame situation and its data， GraphVAE model was modified to complete the graph structure data of wargame situation. Finally, a method for calculating the position of the enemy operator based on the completed graph structure data was designed. The effectiveness and feasibility of the proposed method were verified by experiments. [ABSTRACT FROM AUTHOR]

In 1981, Erdős and Hajnal asked whether the sum of the reciprocals of the odd cycle lengths in a graph with infinite chromatic number is necessarily infinite. Let \mathcal {C}(G) be the set of cycle lengths in a graph G and let \mathcal {C}_{\mathrm {odd}}(G) be the set of odd numbers in \mathcal {C}(G). We prove that, if G has chromatic number k, then \sum _{\ell \in \mathcal {C}_{\mathrm {odd}}(G)}1/\ell \geq (1/2-o_k(1))\log k. This solves Erdős and Hajnal's odd cycle problem, and, furthermore, this bound is asymptotically optimal. In 1984, Erdős asked whether there is some d such that each graph with chromatic number at least d (or perhaps even only average degree at least d) has a cycle whose length is a power of 2. We show that an average degree condition is sufficient for this problem, solving it with methods that apply to a wide range of sequences in addition to the powers of 2. Finally, we use our methods to show that, for every k, there is some d so that every graph with average degree at least d has a subdivision of the complete graph K_k in which each edge is subdivided the same number of times. This confirms a conjecture of Thomassen from 1984. [ABSTRACT FROM AUTHOR]

The Grundy number of a graph G is the maximum number k of colors used to color the vertices of G such that the coloring is proper and every vertex u colored with color i, 1 ≤ i ≤ k, is adjacent to i - 1 vertices colored with each color j, 1 ≤ j ≤ i - 1. In this paper we obtain the Grundy number of corona product of some graphs, denoted by G • H. First, we consider the graph G be 2-regular graph and H be a cycle, complete bipartite, ladder graph and fan graph. Also we consider the graph G and H be a complete bipartite graphs, fan graphs. [ABSTRACT FROM AUTHOR]

Given a finite simple graph G $G$, an odd cover ofG $G$ is a collection of complete bipartite graphs, or bicliques, in which each edge of G $G$ appears in an odd number of bicliques, and each nonedge of G $G$ appears in an even number of bicliques. We denote the minimum cardinality of an odd cover of G $G$ by b2(G) ${b}_{2}(G)$ and prove that b2(G) ${b}_{2}(G)$ is bounded below by half of the rank over F2 ${{\mathbb{F}}}_{2}$ of the adjacency matrix of G $G$. We show that this lower bound is tight in the case when G $G$ is a bipartite graph and almost tight when G $G$ is an odd cycle. However, we also present an infinite family of graphs which shows that this lower bound can be arbitrarily far away from b2(G) ${b}_{2}(G)$. Babai and Frankl proposed the "odd cover problem," which in our language is equivalent to determining b2(Kn) ${b}_{2}({K}_{n})$. In this paper, we determine that b2(Kn) ${b}_{2}({K}_{n})$ is n∕2 $n\unicode{x02215}2$ when 8∣n $8| n$ and is (n+1)∕2 $(n+1)\unicode{x02215}2$ when n $n$ is equivalent to 1 or −1 $-1$ modulo 8. [ABSTRACT FROM AUTHOR]

The Turán number ex(n,H) $\text{ex}(n,H)$ is the maximum number of edges in an H $H$‐free graph on n $n$ vertices. Let T $T$ be any tree. The odd‐ballooning of T $T$, denoted by To ${T}_{o}$, is a graph obtained by replacing each edge of T $T$ with an odd cycle containing the edge, and all new vertices of the odd cycles are distinct. In this paper, we determine the exact value of ex(n,To) $\text{ex}(n,{T}_{o})$ for sufficiently large n $n$ and To ${T}_{o}$ being good, which generalizes all the known results on ex(n,To) $\text{ex}(n,{T}_{o})$ for T $T$ being a star, due to Erdős, Füredi, Gould, and Gunderson (1995), Hou, Qiu, and Liu (2018), and Yuan (2018), and provides some counterexamples with chromatic number three to a conjecture of Keevash and Sudakov (2004), on the maximum number of edges not in any monochromatic copy of H $H$ in a 2‐edge‐coloring of a complete graph of order n $n$. [ABSTRACT FROM AUTHOR]

The partially balanced incomplete block (PBIB)-designs and association schemes arising from different graph parameters is a well-studied concept. In this paper, we define and construct PBIB-designs with association schemes in strongly regular graphs through the nodes belonging to the diametral paths as blocks. A (v , b , r , k , λ , μ) -design, called a diametral-design (in short) over a strongly regular graph G = (V , E) of degree d , diameter diam (G) , is an ordered pair D = (V , B) , where V = V (G) and B is the set of all diametral paths of G , called blocks, containing the nodes belonging to the diametral paths, satisfying the following conditions: (i) If x , y ∈ V and { x , y } ∈ E , then there are exactly λ blocks containing { x , y } ; (ii) If x , y ∈ V , x ≠ y and { x , y } ∉ E , then there are exactly μ -blocks containing { x , y }. We construct PBIB-designs with two-association schemes through diametral paths corresponding to the strongly regular graphs such as the square lattice graphs L 2 (n) , the triangular graphs T (n) , the three Chang graphs, the Petersen graph, the Shrikhande graph, the Clebsch graph, the complement of Clebsch graph, the complement of Schläfli graph, complete bipartite graphs, the Hoffman–Singleton graph, etc. and in each case we give the composition of the diametral paths. These serve as extensions for the collection of near impossible class of strongly regular graphs with given parameters having two-association schemes. [ABSTRACT FROM AUTHOR]