Search

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

Marine container terminal (MCT) plays a key role in the marine intelligent transportation system and international logistics system. However, the efficiency of resource scheduling significantly influences the operation performance of MCT. To solve the practical resource scheduling problem (RSP) in MCT efficiently, this paper has contributions to both the problem model and the algorithm design. Firstly, in the problem model, different from most of the existing studies that only consider scheduling part of the resources in MCT, we propose a unified mathematical model for formulating an integrated RSP. The new integrated RSP model allocates and schedules multiple MCT resources simultaneously by taking the total cost minimization as the objective. Secondly, in the algorithm design, a pre-selection-based ant colony system (PACS) approach is proposed based on graphic structure solution representation and a pre-selection strategy. On the one hand, as the RSP can be formulated as the shortest path problem on the directed complete graph, the graphic structure is proposed to represent the solution encoding to consider multiple constraints and multiple factors of the RSP, which effectively avoids the generation of infeasible solutions. On the other hand, the pre-selection strategy aims to reduce the computational burden of PACS and to fast obtain a higher-quality solution. To evaluate the performance of the proposed novel PACS in solving the new integrated RSP model, a set of test cases with different sizes is conducted. Experimental results and comparisons show the effectiveness and efficiency of the PACS algorithm, which can significantly outperform other state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

A total dominating set in a graph G is a set S of vertices of G such that every vertex in G is adjacent to a vertex in S. Recently, the following question was proposed: "Is it true that every connected cubic graph containing a 3-cycle has two vertex disjoint total dominating sets?" In this paper, we give a negative answer to this question. Moreover, we prove that if we replace 3-cycle with 4-cycle the answer is affirmative. This implies every connected cubic graph containing a diamond (the complete graph of order 4 minus one edge) as a subgraph can be partitioned into two total dominating sets, a result that was proved in 2017. [ABSTRACT FROM AUTHOR]

Event extraction aims to extract human-interest information from massive amounts of unstructured text. Currently, most existing event extraction methods are based on general corpora and rarely consider domain- specific prior knowledge. Moreover, most methods cannot handle well the case where multiple events exist in the same document, and they perform poorly when faced with a large number of negative examples. To address these issues, this paper proposes a model called Fin-PTPCG based on Fin-BERT (financial bidirectional encoder representation from Transformers) and PTPCG (pseudo-trigger-aware pruned complete graph). This method fully utilizes the expression ability of the Fin-BERT pre- training model and incorporates domain- specific prior knowledge during the encoding stage. In the event detection module, multiple binary classifiers are stacked to ensure that the model can effectively identify the situation of multiple events in a document and screen out negative examples. Combined with the decoding module of the PTPCG model, entities are extracted and connected into a complete graph and pruned by calculating a similarity matrix. The problem of unlabeled triggers is solved by selecting pseudo-triggers. Finally, the event extraction is achieved by the event classifier. This method achieves a 0.7 and 3.7 percentage points improvement in F1 score compared to the baselines on the ChFinAnn and Duee-fin datasets for the event extraction task. [ABSTRACT FROM AUTHOR]

The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. In this paper, we investigate the following three properties: containing a complete graph of order k, having the chromatic number at least k, and not having an independent set of size at least k. [ABSTRACT FROM AUTHOR]

If X = (V (X), E(X)) and Y = (V (Y), E(Y)) are n-vertex graphs, then their friends-and-strangers graph FS(X, Y) is the graph whose vertices are the bijections from V (X) to V (Y) in which two bijections σ and σ 0 are adjacent if and only if there is an edge {a, b} ∈ E(X) such that {σ(a), σ(b)} ∈ E(Y) and σ 0 = σ ' (a b), where (a b) is the permutation of V (X) that swaps a and b. We prove general theorems that provide necessary and/or sufficient conditions for FS(X, Y) to be connected. As a corollary, we obtain a complete characterization of the graphs Y such that FS(Dandk,n, Y) is connected, where Dandk,n is a dandelion graph; this substantially generalizes a theorem of the first author and Kravitz in the case k = 3. For specific choices of Y, we characterize the spider graphs X such that FS(X, Y) is connected. In a different vein, we study the cycle spaces of friends-andstrangers graphs. Naatz proved that if X is a path graph, then the cycle space of FS(X, Y) is spanned by 4-cycles and 6-cycles; we show that the same statement holds when X is a cycle and Y has domination number at least 3. When X is a cycle and Y has domination number at least 2, our proof sheds light on how walks in FS(X, Y) behave under certain Coxeter moves. [ABSTRACT FROM AUTHOR]

Given an edge-coloring of a graph G, G is said to be rainbow if any two edges of G receive different colors. The anti-Ramsey number AR(G, H) is defined to be the maximum integer k such that there exists a k-edgecoloring of G avoiding rainbow copies of H. The anti-Ramsey number for graphs, especially matchings, have been studied in several graph classes. Gilboa and Roditty focused on the anti-Ramsey number of graphs with small components, especially including a matching. In this paper, we continue the work in this direct and determine the exact value of the anti-Ramsey number of K4 ∪ tP2 in complete graphs. Also, we improve the bound and obtain the exact value of AR(Kn, C3 ∪ tP2) for all n ≥ 2t + 3. [ABSTRACT FROM AUTHOR]

In a (G¹, G²) coloring of a graph G, every edge of G is in G¹ or G². For two bipartite graphs H1 and H2, the bipartite Ramsey number BR(H1, H2) is the least integer b ≥ 1, such that for every (G¹, G²) coloring of the complete bipartite graph Kb,b, results in either H1 ⊆ G¹ or H2 ⊆ G². As another view, for bipartite graphs H1 and H2 and a positive integer m, the m-bipartite Ramsey number BRm(H1, H2) of H1 and H2 is the least integer n (n ≥ m) such that every subgraph G of Km,n results in H1 ⊆ G or H2 ⊆ G. The size of m-bipartite Ramsey number BRm(K2,2, K2,2), the size of m-bipartite Ramsey number BRm(K2,2, K3,3) and the size of m-bipartite Ramsey number BRm(K3,3, K3,3) have been computed in several articles up to now. In this paper we determine the exact value of BRm(K2,2, K4,4) for each m ≥ 2. [ABSTRACT FROM AUTHOR]

The crossing number of a graph is a significant measure that indicates the complexity of the graph and the difficulty of visualizing it. In this paper, we examine the crossing numbers of join products involving the complete graph K 5 with discrete graphs, paths, and cycles. We analyze optimal drawings of K 5 , identify all five non-isomorphic drawings, and address previously hypothesized crossing numbers for K 5 + P n , and K 5 + C n . Through a simplified approach, we first establish cr (K 5 + D n) and then extend our method to prove the crossing numbers cr (K 5 + P n) and cr (K 5 + C n) . These results also lead to new hypotheses for cr (W m + S n) and cr (W m + W n) involving wheels and stars. Our findings correct previous inaccuracies in the literature and provide a foundation for future research. [ABSTRACT FROM AUTHOR]

A subset S of non-negative integers N o is called a numerical semigroup if it is a submonoid of N o and has a finite complement in N o . An undirected graph G (S) associated with S is a graph having V (G (S)) = { v i : i ∈ N o ∖ S } and E (G (S)) = { v i v j ⇔ i + j ∈ S } . In this article, we propose a conjecture for the clique number of graphs associated with a symmetric family of numerical semigroups of arbitrary multiplicity and embedding dimension. Furthermore, we prove this conjecture for the case of arbitrary multiplicity and embedding dimension 7. [ABSTRACT FROM AUTHOR]

We continue the study of (tw , ω) -bounded graph classes, that is, hereditary graph classes in which the treewidth can only be large due to the presence of a large clique, with the goal of understanding the extent to which this property has useful algorithmic implications for the Maximum Independent Set and related problems. In the previous paper of the series [Dallard, Milanič, and Štorgel, Treewidth versus clique number. II. Tree-independence number, J. Comb. Theory, Ser. B, 164 (2024) 404–442], we introduced the tree-independence number , a min-max graph invariant related to tree decompositions. Bounded tree-independence number implies both (tw , ω) -boundedness and the existence of a polynomial-time algorithm for the Maximum Weight Independent Packing problem, provided that the input graph is given together with a tree decomposition with bounded independence number. In particular, this implies polynomial-time solvability of the Maximum Weight Independent Set problem. In this paper, we consider six graph containment relations—the subgraph, topological minor, and minor relations, as well as their induced variants—and for each of them characterize the graphs H for which any graph excluding H with respect to the relation admits a tree decomposition with bounded independence number. The induced minor relation is of particular interest: we show that excluding either a K 5 minus an edge or the 4-wheel implies the existence of a tree decomposition in which every bag is a clique plus at most 3 vertices, while excluding a complete bipartite graph K 2 , q implies the existence of a tree decomposition with independence number at most 2 (q − 1). These results are obtained using a variety of tools, including ℓ -refined tree decompositions, SPQR trees, and potential maximal cliques, and actually show that in the bounded cases identified in this work, one can also compute tree decompositions with bounded independence number efficiently. Applying the algorithmic framework provided by the previous paper in the series leads to polynomial-time algorithms for the Maximum Weight Independent Set problem in an infinite family of graph classes, each of which properly contains the class of chordal graphs. In particular, these results apply to the class of 1-perfectly orientable graphs, answering a question of Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius from 2019. [ABSTRACT FROM AUTHOR]

A graph is O k -free if it does not contain k pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite graphs as subgraphs) O k -free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is optimal, as there is an infinite family of O 2 -free graphs without K 2 , 3 as a subgraph and whose treewidth is (at least) logarithmic. Using our result, we show that Maximum Independent Set and 3-Coloring in O k -free graphs can be solved in quasi-polynomial time. Other consequences include that most of the central NP-complete problems (such as Maximum Independent Set , Minimum Vertex Cover , Minimum Dominating Set , Minimum Coloring) can be solved in polynomial time in sparse O k -free graphs, and that deciding the O k -freeness of sparse graphs is polynomial time solvable. [ABSTRACT FROM AUTHOR]

A simple graph G on n vertices is partition-good if and only if for all pairs (a, b) of positive integers such that a+b = n, V (G) can be partitioned into sets A,B satisfying: |A| = a, |B| = b, and G[A],G[B] are connected. G is partition-wonderful if and only if either (i) n = 1, or (ii) n > 1, G is connected, and of all pairs (a, b) of positive integers such that a + b = n, V (G) can be partitioned into sets A,B satisfying: |A| = a, |B| = b, and G[A],G[B] are partition-wonderful. We characterize the partition-good and the partition-wonderful among the complete multipartite graphs, and, along the way, prove some elementary results about these graph properties. [ABSTRACT FROM AUTHOR]

This paper investigates a leader–follower consensus problem of multi-layer networks and understands the role of leader's allocations in the process of consensus. Leader–follower coherence quantified by the spectrum measures the extent of consensus between leaders and followers in the system under additive noise. In order to study the exact interplay between leader–follower coherence and leader's allocations, we choose complete multi-partite networks as network models and assign the leaders into different layers. Based on the network construction, we obtain exact solutions of leader–follower coherence with freely assigned leaders and reveal that the allocations of leaders have a significant impact on the coherence. Finally, we compare the leader–follower coherence and leaderless coherence of bipartite networks when the number of leaders and network size satisfies certain conditions. [ABSTRACT FROM AUTHOR]

We study the weak Ks ${K}_{s}$‐saturation number of the Erdős–Rényi random graph G(n,p) ${\mathbb{G}}(n,p)$, denoted by wsat(G(n,p),Ks) $\text{wsat}({\mathbb{G}}(n,p),{K}_{s})$, where Ks ${K}_{s}$ is the complete graph on s $s$ vertices. In 2017, Korándi and Sudakov proved that the weak Ks ${K}_{s}$‐saturation number of Kn ${K}_{n}$ is stable, in the sense that it remains the same after removing edges with constant probability. In this paper, we prove that there exists a threshold for this stability property and give upper and lower bounds on the threshold. This generalizes the result of Korándi and Sudakov. A general upper bound on wsat(G(n,p),Ks) $\text{wsat}({\mathbb{G}}(n,p),{K}_{s})$ is also provided. [ABSTRACT FROM AUTHOR]

Tea planting has developed rapidly in China in recent years. It is of ever-increasing importance to integrate massive and complex knowledge in a structured manner, particularly with the development of the internet. The diverse and scattered sources of tea planting have resulted in fragmented knowledge. Knowledge graphs can be expected to greatly enhance the manageability and accessibility of data. However, it is also still lacking in the complete knowledge graphs of tea planting. It is of great significance to promote the informatization and modernization of the entire tea industry. In this study, a systematic and structured knowledge graph of tea planting was constructed on the orderly knowledge resources for the tea planting field. A teaplanting knowledge graph completion (TPKGC) model was integrated into the relationship context and path for the missing relationships between entities in the tea-planting knowledge graph. The improved model consisted mainly of three parts: a relationship context layer, a relationship path layer, and a fusion output layer. In the relationship context layer, the TeaConAggr (tea context aggregate) module was first used to aggregate the hop relationship contexts of entities. After that, the hop relationship contexts were summarized to obtain the relational context of entity pairs using a multi-layer relational messaging mechanism. In the relationship path layer, the relationship path aggregation module was used to aggregate the relationship paths among entities. The relationship path learning module was used to learn the paths. In the fusion output layer, multiplication attention and Softmax function were used to fuse the relationship context representation from the relationship context layer with the relationship path feature from the relationship path layer, in order to obtain the weight of each path. Subsequently, the weight was calculated with the relationship path feature to obtain the aggregated representation of the relationship path. Finally, additive attention was used to process the relationship context representation. The relationship path that aggregated representation was obtained for the predicted ranking of relationships between entity pairs, in order to achieve the goal of knowledge graph relationship completion. Data collection was constructed a knowledge graph in the field of tea planting. There were two major types of resources: books and the internet. The dataset was defined as 16 entity and 16 relationship types to represent various entities and their complex relationships in the tea planting knowledge graph. The TPKGData dataset was also developed for the tea-planting knowledge graph. The experimental results showed that the performance of the improved model was achieved in 85.40%, 80.95%, and 90.08% on the Mean Reciprocal Rank, Hits@1, and Hits@3 metrics, respectively, which were 2.56, 2.63, and 4.25 percentage points higher than those of Shallom model. The effectiveness of the model was fully met to predict the missing relationships between entities in the tea-planting knowledge graph. In addition, the comparative experiments were also conducted on the publicly available datasets FB15K-237 and WN18RR, in order to further verify the generalization of the model. At the same time, the TPKGC model also achieved the best performance on these datasets. Therefore, the model was performed outstandingly on the specific domain datasets, indicating better generalization. The stable performance was achieved in the different datasets of the knowledge graph. The TPKGC model demonstrated excellent performance and generalization potential in the task of relationship completion within the teaplanting knowledge graph. The finding can also provide important guidance for the construction of knowledge graphs. [ABSTRACT FROM AUTHOR]

We construct 2-step nilpotent Lie algebras using labeled directed simple graphs and give a criterion to detect certain ideals and subalgebras by finding special subgraphs. We prove that if a label occurs only once, then reversing its orientation leads to an isomorphic algebra. As a consequence, if every edge is labeled differently, the Lie algebra depends only on the underlying undirected graph. In addition, we construct the graphs of all 2-step nilpotent Lie algebras of dimension ≤ 6 and compute the algebra of strata preserving derivations of the Lie algebra associated with the complete bipartite graph K m , n with two different labelings. [ABSTRACT FROM AUTHOR]

The eccentricity matrix of a graph is obtained from the distance matrix by keeping the entries that are largest in their row or column, and replacing the remaining entries by zero. This matrix can be interpreted as an opposite to the adjacency matrix, which is on the contrary obtained from the distance matrix by keeping only the entries equal to 1. In the paper, we determine graphs having the second largest eigenvalue of eccentricity matrix less than 1. [ABSTRACT FROM AUTHOR]

The property of fuzziness is advantageous for any setting where a problem prediction and solution are intended. In comparison to the classical approach (crisp set), fuzzy graphs are beneficial as they provide greater precision and flexibility. Intuitionistic fuzzy graphs (IFGs) are generalizations of fuzzy graphs, in which each vertex is allocated an ordered pair whose first coordinate represents the membership value and whose second coordinate gives the non-membership value. Sombor indices are recently invented indices and are prime indices in describing the topology of a graph. They have demonstrated strong prediction ability in mathematical chemistry. The main aim of this research draft is to define two milestones, the fifth and sixth versions of Sombor indices in an intuitionistic fuzzy environment, IFGs are much more generalized and universal as compared to crisp graph theory, so we converted these two topological indices in this environment and then formulae for some fundamental families of graphs such as path graph, cycle graph, complete graph etc. are being derived. Our manuscript presents a novel application of opening a chain of schools of a popular brand in a certain vicinity, including the cluster center of the chain and applying intuitionistic fuzzy-based topological indices to assess their performance. With the help of this application, we highlight the practical implications and benefits of employing intuitionistic fuzzy-based techniques on the performance of schools through a comparative analysis. We checked the importance of intuitionistic fuzzy Sombor indices by presenting the application and concluded these indices can be applied to decision-making problems. With the help of the application, the efficiency of both of the intuitionistic fuzzy Sombor indices is also characterized, which must be a future efficacious tool in decision-making issues. [ABSTRACT FROM AUTHOR]

Finding a group of dominant servers is a necessary step towards optimising service provisioning to all clients in the complex world of server-client networks. This crucial decision rests on the non-split dominance number in the graph architecture. We present the idea of an equitable non-split domination number in graphs to address the possible problem of unequal task distribution among servers. When the vertices of a dominating set, Dens, have the same colour in an equitable colouring scheme, the set is said to be equitable. The induced subgraph V - D also maintains its connectivity. In particular, the application of equitable non-split domination numbers to graphs like the Triangular Grid, Antiprism, Wheel, and Complete Graphs is explored in this study. [ABSTRACT FROM AUTHOR]

R. Lyons, R. Pemantle and Y. Peres (Ann. Probab. 24 (4), 1996, 1993–2006) conjectured that for a Cayley graph G with a growth rate gr(G) > 1, the speed of a biased random walk exists and is positive for the biased parameter λ ∈ (1, gr(G)). And Gabor Pete (Probability and geometry ´ on groups, Chaper 9, 2024) sheds light on the intricate relationship between the spectral radius of the graph and the speed of the biased random walk. Here, we focus on an example of a Cayley graph, a free product of complete graphs. In this paper, we establish the continuity of the spectral radius of biased random walks with respect to the bias parameter in this class of Cayley graphs. Our method relies on the Kesten-Cheeger-Dodziuk-Mohar theorem and the analysis of generating functions. [ABSTRACT FROM AUTHOR]

A graph is well-covered if all of its maximal independent sets have the same size. A graph that remains well-covered upon the removal of any vertex is called a 1-well-covered graph. These graphs, when they have no isolated vertices, are also known asW2 graphs. It is well-known that every graph G W2 has two disjoint maximum independent sets. In this paper, we investigate connected W2 graphs with n vertices that contain a clique of size n/3. We prove that if the removal of two disjoint maximum independent sets from a graph G W2 leaves a clique of size at least 3, then G contains a clique of size n/3. Using this result, we provide a complete characterization of these graphs, based on eleven graph families. [ABSTRACT FROM AUTHOR]

A graph is called split if its vertex set can be partitioned into a stable set and a clique. In this article, we studied two variants of split graphs. A graph G is polar if its vertex set can be partitioned into two sets A and B such that G[A] is a complete multipartite graph and G[B] is a disjoint union of complete graphs. A 2-unipolar graph is a polar graph G such that G[A] is a clique and G[B] is the disjoint union of complete graphs with at most two vertices. We present a minimal forbidden induced subgraph characterization for 2-unipolar graphs. In addition, we show that they can be represented as an intersection of substars of special cacti. Let G be a graph class, the G-width of a graph G is the minimum positive integer k such that there exist k independent sets N1, ... , Nk such that a set F of nonedges of G, whose endpoints belong to some Ni with i = 1, ... , k, can be added so that the resulting graph G′ belongs to G. We say that a graph G is k-probe-G if it has G-width at most k and when G is the class of split graphs it is denominated k-probe-split. We prove that deciding, given a graph G and a positive integer k, whether G is a h-probe-split graph for some h ≤ k is NP-complete. Besides, a characterization by minimal forbidden induced subgraphs for 2-probe-split cographs is presented. [ABSTRACT FROM AUTHOR]

This work presents a new encryption technique that ensures safe communication through two distinct phases: utilizing monoalphabetic substitution ciphers that rely on agreed-upon character-swapping arrangements between authorized individuals and applying an alphabetical encryption table. In addition, the research utilizes the Kurskal technique to calculate the minimum spanning tree, which improves security by creating intricate encrypted text using a shared key based on ideas drawn from graph theory. [ABSTRACT FROM AUTHOR]

We have discovered the distinctive polynomial of the complete graph’s Laplacian matrix with this article in mind. The trace of the Laplacian matrix and the total number of vertices in the complete graph were used to determine the coefficients of the characteristic polynomial. Additionally, we have demonstrated that Laplacian eigenvalues can be used to get coefficients for identical characteristic polynomials. Can be used to get coefficients for identical characteristic polynomials. [ABSTRACT FROM AUTHOR]

Nowadays QKD plays a critical role in unconditionally-secure and quantum-safe key distribution. Commercially available QKD devices are getting more popular for institutional and governmental national and international networks, but are expensive and offer limited key rates. We provide a formalization of QKD-generated key forwarding and redistribution at the KMS level by extending the network graph of physical QKD links to the complete graph with logical links, and we investigate its application on three practical scalable scenarios (all-to-all, one-to-all, one-to-one). We define a maximization goal for each scenario, and provide a linear programming problem statement to compute the optimal redistribution. We perform an extensive analysis of the algorithm in terms of forwarding results and key consumption on simulated QKD networks and discuss the implications of network size and graph topology on the algorithm's performance and complexity. [ABSTRACT FROM AUTHOR]

In 1975, Erd̋s asked the following question: What is the maximum number of edges that an |$n$| -vertex graph can have without containing a cycle with all diagonals? Erd̋s observed that the upper bound |$O(n^{5/3})$| holds since the complete bipartite graph |$K_{3,3}$| can be viewed as a cycle of length six with all diagonals. In this paper, we resolve this old problem. We prove that there exists a constant |$C$| such that every |$n$| -vertex graph with at least |$Cn^{3/2}$| edges contains a cycle with all diagonals. Since any cycle with all diagonals contains cycles of length four, this bound is best possible using well-known constructions of graphs without four-cycles based on finite geometry. Among other ideas, our proof involves a novel lemma about finding an almost-spanning robust expander, which might be of independent interest. [ABSTRACT FROM AUTHOR]

The normalized distance Laplacian of a graph G is defined as D L (G) = T (G) − 1 / 2 (T (G) − D (G)) T (G) − 1 / 2 where D (G) is the matrix with pairwise distances between vertices and T (G) is the diagonal transmission matrix. In this project, we study the minimum and maximum spectral radii associated with this matrix, and the structures of the graphs that achieve these values. In particular, we prove a conjecture of Reinhart that the complete graph is the unique graph with minimum spectral radius, and we give several partial results towards a second conjecture of Reinhart regarding which graph has the maximum spectral radius. [ABSTRACT FROM AUTHOR]

In an edge-colored graph G , let d m o n (v) denote the maximum number of edges with the same color incident with a vertex v in G , called the monochromatic-degree of v. The maximum value of d m o n (v) over all vertices v ∈ V (G) is called the maximum monochromatic-degree of G , denoted by Δ m o n (G). Li et al. in 2019 conjectured that every edge-colored complete graph G of order n with Δ m o n (G) ≤ n − 3 k + 1 contains k vertex-disjoint properly colored (PC for short) cycles of length at most 4, and they showed that the conjecture holds for k = 2. Han et al. showed that every edge-colored complete graph G of order n with Δ m o n (G) ≤ n − 2 k contains k PC cycles of different lengths. They further got the condition Δ m o n (G) ≤ n − 6 for the existence of two vertex-disjoint PC cycles of different lengths. In this paper, we consider the problems of the existence of edge-disjoint PC cycles of length at most 4 (different lengths) in an edge-colored complete graph G of order n. [ABSTRACT FROM AUTHOR]

In this paper a continuous-time evolving random graph model is defined and examined. The main units of the model are complete graphs on N vertices, where $ N \geq ~3 $ N ≥ 3 is a fixed integer. At each birth event a new vertex and random number of edges are added to the graph. The asymptotic behaviour of the number of vertices and the asymptotic behaviour of the number of m-cliques ( $ 2\leq m\leq N $ 2 ≤ m ≤ N) are studied. The proofs are based on general results of the theory of branching processes. [ABSTRACT FROM AUTHOR]

We contribute to the efficient approximation of the Pareto-set for the classical NP -hard multiobjective minimum spanning tree problem (moMST) adopting evolutionary computation. More precisely, by building upon preliminary work, we analyze the neighborhood structure of Pareto-optimal spanning trees and design several highly biased sub-graph-based mutation operators founded on the gained insights. In a nutshell, these operators replace (un)connected sub-trees of candidate solutions with locally optimal sub-trees. The latter (biased) step is realized by applying Kruskal's single-objective MST algorithm to a weighted sum scalarization of a sub-graph. We prove runtime complexity results for the introduced operators and investigate the desirable Pareto-beneficial property. This property states that mutants cannot be dominated by their parent. Moreover, we perform an extensive experimental benchmark study to showcase the operator's practical suitability. Our results confirm that the sub-graph-based operators beat baseline algorithms from the literature even with severely restricted computational budget in terms of function evaluations on four different classes of complete graphs with different shapes of the Pareto-front. [ABSTRACT FROM AUTHOR]

Let G and H be two graphs, each one of them being a path, a cycle or a star. In this paper, we determine the b-chromatic number of every subdivision-vertex neighbourhood corona G ⊡ H or G ⊡ Kn, where Kn is the complete graph of order n. It is also established for those graphs Kn ⊡ G having m-degree not greater than n + 2. All the proofs are accompanied by illustrative examples. [ABSTRACT FROM AUTHOR]

Since Grover developed a quantum search algorithm for unstructured data, generalizing the algorithm to structured datasets, which can be represented as graphs, has been an important research topic. Recently, Krovi et al. introduced a quantum algorithm that can find a marked vertex on any ergodic and reversible graph by using absorbing marked vertices, replacing the marked vertices with partially absorbing vertices. The algorithm was extended to finding marked vertices in any graph with multiple marked vertices using the quantum fast-forwarding technique (QFF). However, the proof of this result based on QFF does not provide much intuition about the underlying mechanism. In this paper, to obtain the underlying mechanism of the quantum search with absorbing marked vertices, we consider, as a nontrivial example, the complete bipartite graph consisting of two sets X 1 and X 2 with the marked vertices being on both vertex sets. By analytically finding the spectral information of the quantum walk, we propose an approximate optimal search parameter s o . We demonstrate that the quantum algorithm at the optimal search parameter s o shows a quadratic speedup compared to the corresponding classical search method if the number of marked vertices is smaller than the total number of vertices. Additionally, we find that the quantum search is described in terms of a two-state model for that case. [ABSTRACT FROM AUTHOR]

Encryption and decryption are the two processes in the cryptosystem that ensure the safe transfer of data or sensitive information. Apart from classical mathematics, graph theory techniques are employed nowadays to construct a strong cryptosystem. This paper uses graph techniques such as decomposition and labelling to encrypt and decrypt an alphanumeric string of length 8. The novelty of this paper is the introduction of (S9,C3)-multi-decomposition and a new labelling technique - anti-magic decomposed labelling, which is applied in the cryptosystem. [ABSTRACT FROM AUTHOR]

Laplacian matrix and its spectrum are commonly used for giving a measure in networks in order to analyse its topological properties. In this paper, Laplacian matrix of graphs and their spectrum are studied. Laplacian energy of a graph G of order n is defined as LE (G) = ∑ i = 1 n | λ i (L) - d ¯ | , where λ i (L) is the i-th eigenvalue of Laplacian matrix of G, and d ¯ is their average. If LE (G) = LE (K n) for the complete graph K n of order n, then G is known as L-borderenergetic graph. In the first part of this paper, we construct three infinite families of non-complete disconnected L-borderenergetic graphs: Λ 1 = { G b , j , k = [ (((j - 2) k - 2 j + 2) b + 1) K (j - 1) k - (j - 2) ] ∪ b (K j × K k) | b , j , k ∈ Z + } , Λ 2 = { G 2 , b = [ K 6 ∇ b (K 2 × K 3) ] ∪ (4 b - 2) K 9 | b ∈ Z + } , Λ 3 = { G 3 , b = [ b K 8 ∇ b (K 2 × K 4) ] ∪ (14 b - 4) K 8 b + 6 | b ∈ Z + } , where ∇ is join operator and × is direct product operator on graphs. Then, in the second part of this work, we construct new infinite families of non-complete connected L-borderenergetic graphs Ω 1 = { K 2 ∇ a K 2 r ¯ | a ∈ Z + } , Ω 2 = { a K 3 ∪ 2 (K 2 × K 3) ¯ | a ∈ Z + } and Ω 3 = { a K 5 ∪ (K 3 × K 3) ¯ | a ∈ Z + } , where G ¯ is the complement operator on G. [ABSTRACT FROM AUTHOR]

A simple undirected regular graph is said to be semisymmetric if it is edge-transitive but not vertex-transitive. For a semisymmetric graph Γ of order 2 p 3 , p a prime, it is well known that Γ is bipartite with two biparts having equal size. The complete classification of such graphs has been given for the full automorphism group Aut (Γ) acting unfaithfully on at least one bipart of Γ , which shows that there is only one infinite family of such graphs with valency p 2. The graphs of this kind have been determined when Aut (Γ) acts faithfully and primitively on at least one bipart of Γ , and thus there is only one remaining case for classifying such graphs of valency p 2 , Aut (Γ) acting faithfully and imprimitively on both biparts of Γ , which is dealt with in this paper. As a result, there is only one infinite family of semisymmetric graphs of order 2 p 3 with valency p 2. [ABSTRACT FROM AUTHOR]

Can we efficiently compute optimal solutions to instances of a hard problem from optimal solutions to neighbor instances, that is, instances with one local modification? For example, can we efficiently compute an optimal coloring for a graph from optimal colorings for all one-edge-deleted subgraphs? Studying such questions not only gives detailed insight into the structure of the problem itself, but also into the complexity of related problems, most notably, graph theory's core notion of critical graphs (e.g., graphs whose chromatic number decreases under deletion of an arbitrary edge) and the complexity-theoretic notion of minimality problems (also called criticality problems, e.g., recognizing graphs that become 3-colorable when an arbitrary edge is deleted). We focus on two prototypical graph problems, colorability and vertex cover. For example, we show that it is NP -hard to compute an optimal coloring for a graph from optimal colorings for all its one-vertex-deleted subgraphs, and that this remains true even when optimal solutions for all one-edge-deleted subgraphs are given. In contrast, computing an optimal coloring from all (or even just two) one-edge-added supergraphs is in P . We observe that vertex cover exhibits a remarkably different behavior, demonstrating the power of our model to delineate problems from each other more precisely on a structural level. Moreover, we provide a number of new complexity results for minimality and criticality problems. For example, we prove that Minimal-3-UnColorability is complete for DP (differences of NP sets), which was previously known only for the more amenable case of deleting vertices rather than edges. For vertex cover, we show that recognizing β -vertex-critical graphs is complete for Θ 2 p (parallel access to NP ), obtaining the first completeness result for a criticality problem for this class. [ABSTRACT FROM AUTHOR]

Changes of mind can become less likely the longer an agent has adopted a given opinion state. This resilience or inertia to change has been called "aging". We perform a comparative study of the effects of aging on the critical behavior of two standard opinion models with pairwise interactions. One of them is the voter model, which is a two-state model with a dynamic that proceeds via social contagion; another is the so-called kinetic exchange model, which allows a third (neutral) state, and its formed opinion depends on the previous opinions of both interacting agents. Furthermore, in the noisy version of both models, random opinion changes are also allowed, regardless of the interactions. Due to aging, the probability of changing diminishes with the age, and to take this into account, we consider algebraic and exponential kernels. We investigate the situation where aging acts only on pairwise interactions. Analytical predictions for the critical curves of the order parameters are obtained for the opinion dynamics on a complete graph, in good agreement with agent-based simulations. For both models considered, the consensus is optimized via an intermediate value of the parameter that rules the rate of decrease of the aging factor. [ABSTRACT FROM AUTHOR]

We study in this paper a variation of the acclaimed carrier sense multiple access (CSMA) protocol. A random access algorithm is where back-off rates depend on the state of the network through queue lengths. We provide the first case where full proof of convergence to fluid limits can be obtained. Although this has been often justified informally, this is the first proof dedicated to obtaining this result formally. We then outline the difficulties arising when queues reach zero and solve them in the case of a complete interference graph. The main contribution of this paper is to provide a formal justification of the fluid limits for a complete interference graph in the case where some initial queue lengths are zero. This is done with a coupling argument. This paper also proves convergence to the fluid limits in the general case up to the time a queue reaches 0 on the fluid scale. [ABSTRACT FROM AUTHOR]

To solve the difficulties in threshold selection and poor performance under low signal‐to‐noise ratio (SNR) conditions in existing spectrum sensing algorithms, a graph‐based spectrum sensing algorithm using nonlinear function regulation was proposed. The idea was to add a specific nonlinear transformation between the normalisation and quantization steps of the existing signal‐to‐graph converter (SGC). If the autocorrelation function of the observed signal selected as the input fed to SGC, the nonlinear function has the ability to adjust the uniformity of its probability distribution, increasing the probability of the observed signal being transformed into a complete graph under the alternative hypothesis, whereas remaining a noncomplete graph under the null hypothesis. Thus transformed the graph‐based spectrum sensing into a complete graph‐detection problem. Based on the theory of dispersive ordering, a theoretical analysis of the mechanism by which nonlinear transformations affect graph connectivity was conducted. The simulation results showed that the detection performance of the proposed algorithm was superior to that of existing graph‐based spectrum sensing algorithms. When SNR was −7 dB, the detection probability of the proposed algorithm exceeded 95%. Moreover, among the existing graph‐based spectrum sensing algorithms, the proposed algorithm exhibited the lowest computational complexity apart from the block range‐based method. [ABSTRACT FROM AUTHOR]

Let G be the complete Euclidean graph on a set of points embedded in the plane. Given a constant t > 1 , a spanning subgraph G ′ of G is said to be a t -spanner, or simply a spanner, if for any pair of nodes p , q in G there exists a t -path in G ′ , i.e., a path between p and q whose length is at most t times their distance in G. Gap-greedy spanner, proposed by Arya and Smid, is a light weight and bounded degree spanner in which a pair of points p , q is guaranteed to have a t -path, if there exists at least one edge with some special criteria in the spanner. Existing algorithms for computing the gap-greedy spanner determine the existence of such an edge for each pair of points by examining the edges of the spanner, which takes O (n) time, however in this paper, we have presented a method by which this task can be done in O (1) time. Using the proposed method and well-separated pair decomposition, we have proposed a linear-space algorithm that can compute the gap-greedy spanner in O (n 2) time. How to use the well-separated pair decomposition to compute this spanner was proposed by Bakhshesh and Farshi, however using an example, we have shown that one of the algorithms they have proposed for this purpose is incorrect. We have performed various experiments to measure the duration and amount of memory used by the algorithms for computing this spanner. The results of these experiments showed that the proposed method, without a significant effect on the amount of memory consumed compared to previous algorithms, leads to a significant acceleration in the construction time of this spanner. [ABSTRACT FROM AUTHOR]

To any simple graph G , the clique graph operator K assigns the graph K (G) , which is the intersection graph of the maximal complete subgraphs of G . The iterated clique graphs are defined by K 0 (G) = G and K n (G) = K (K n - 1 (G)) for n ≥ 1 . We associate topological concepts to graphs by means of the simplicial complex Cl (G) of complete subgraphs of G . Hence, we say that the graphs G 1 and G 2 are homotopic whenever Cl (G 1) and Cl (G 2) are. A graph G such that K n (G) ≃ G for all n ≥ 1 is called K -homotopy permanent. A graph is Helly if the collection of maximal complete subgraphs of G has the Helly property. Let G be a Helly graph. Escalante (1973) proved that K (G) is Helly, and Prisner (1992) proved that G ≃ K (G) , and so Helly graphs are K -homotopy permanent. We conjecture that if a graph G satisfies that K m (G) is Helly for some m ≥ 1 , then G is K -homotopy permanent. If a connected graph has maximum degree at most four and is different from the octahedral graph, we say that it is a low degree graph. It was recently proven that all low-degree graphs G satisfy that K 2 (G) is Helly. In this paper, we show that all low-degree graphs have the homotopy type of a wedge or circumferences, and that they are K -homotopy permanent. [ABSTRACT FROM AUTHOR]

Colour the edges of the complete graph with vertex set { 1 , 2 , ⋯ , n } with an arbitrary number of colours. What is the smallest integer f(l, k) such that if n > f (l , k) then there must exist a monotone monochromatic path of length l or a monotone rainbow path of length k? Lefmann, Rödl, and Thomas conjectured in 1992 that f (l , k) = l k - 1 and proved this for l ⩾ (3 k) 2 k . We prove the conjecture for l ⩾ k 3 (log k) 1 + o (1) and establish the general upper bound f (l , k) ⩽ k (log k) 1 + o (1) · l k - 1 . This reduces the gap between the best lower and upper bounds from exponential to polynomial in k. We also generalise some of these results to the tournament setting. [ABSTRACT FROM AUTHOR]

In this treatise, we discuss existence and uniqueness questions for parametric minimal surfaces in Riemannian spaces, which represent minimal graphs. We choose the Riemannian metric suitably such that the variational solution of the Riemannian Dirichlet integral under Dirichlet boundary conditions possesses a one-to-one projection onto a plane. At first we concentrate our considerations on existence results for boundary value problems. Then we study uniqueness questions for boundary value problems and for complete minimal graphs. Here we establish curvature estimates for minimal graphs on discs, which imply Bernstein-type results. [ABSTRACT FROM AUTHOR]

An edge-coloring of a graph G is an assignment of colors to its edges so that no two edges incident to the same vertex receive the same color. The chromatic index of G, denoted by χ'(G), is the least k for which G has a k edge-coloring. Graphs with χ'(G)=Δ(G) are said to be Class 1, and graphs with χ'(G)=Δ(G)+1 are said to be Class 2. Let G be a graph with V(G)={t1,t2,..., tn}, n≥2, and hn=(Hi)i∈{1,2,...,n} be a sequence of vertex-disjoint graphs with V(Hi)={(ti,y1),(ti,y2),...,(ti,ymi)}, mi≥1. The generalized lexicographic product G[hn] of G and hn=(Hi)i∈{1,2,...,n} is a simple graph with vertex set ⋃ ni=1 V(Hi), in which (ti,yp) is adjacent to (tj,yq) if and only if either ti=tj and (ti,yp)(ti,yq)∈E(Hi) or titj∈E(G). If G is a complete graph with order 2, then G[h2] denotes a join H1+H2 of vertex-disjoint graphs H1 and H2. If Hi≅H for i=1,2,...,n, then G[hn]=G[H], where G[H] denotes the lexicographic product of two graphs G and H. In this paper, we provide sufficient conditions for the generalized lexicographic product G[hn] of G and hn=(Hi)i∈{1,2,...,n} to be Class 1, where all graphs in hn have the same number of vertices. [ABSTRACT FROM AUTHOR]

In this paper, the planar polynomial of a graph is introduced and some of its properties are discussed. The planar polynomial of the graph G is real-rooted if and only if G is planar. This polynomial is not EE-invariant. Some useful results about the roots of planar polynomial of complete graphs are presented. Moreover, all the graphs whose planar polynomial is of degree five are characterized. [ABSTRACT FROM AUTHOR]

Aiming at the problem that the search efficiency of key vulnerable nodes in large-scale networks is not high and the consideration factors are not comprehensive enough, in order to improve the time and space efficiency of search and the accuracy of results, a key vulnerable node discovery method based on Bayesian attack subgraphs and improved fuzzy C-means clustering is proposed. Firstly, the attack graph is divided into Bayesian attack subgraphs, and the analysis results of the complete attack graph are quickly obtained by aggregating the information of the attack path analysis in the subgraph to improve the time and space efficiency. Then, the actual threat features of the vulnerability nodes are extracted from the analysis results, and the threat features of the vulnerability itself in the common vulnerability scoring standard are considered to form the clustering features together. Next, the optimal number of clusters is adaptively adjusted according to the variance idea, and fuzzy clustering is performed based on the extracted clustering features. Finally, the key vulnerable nodes are determined by setting the feature priority. Experiments show that the proposed method can optimize the time and space efficiency of analysis, and the fuzzy clustering considering multiple features can improve the accuracy of analysis results. [ABSTRACT FROM AUTHOR]