Search

Let G = (V , E) be a graph. A set S ⊆ V is a total restrained dominating set if every vertex is adjacent to a vertex in S , and every vertex in V − S is adjacent to a vertex in V − S. The total restrained domination number of G , denoted γ t r (G) , is the smallest cardinality of a total restrained dominating set of G. In this paper we show that if G is a K 1 , ℓ -free graph with δ ≥ ℓ ≥ 3 and δ ≥ 5 , then γ t r (G) ≤ n 1 − (2 δ − 3) (2 δ) δ δ − 1 + o δ (1) . [ABSTRACT FROM AUTHOR]

Diagnosability is a fundamental consideration when designing an interconnected network. The PMC and MM ∗ fault diagnosis models are the two most commonly used models. Both the g -good-neighbour diagnosability and g -extra diagnosability of an interconnection network have been two of the hot topics in the intersectional research areas of Graph theory and Computer Science, which become increasingly attractive for new solutions to real-world problems. However, there are still some problems in the transformation from the concepts of Computer Science to that of mathematics. In this paper, we systematically study such problems and give a strict proof from concepts to mathematical conclusions. In the terms of results, we not only give the relationship between g -good-neighbour diagnosabilities of the network under PMC model and MM ∗ model, but also between g -extra diagnosabilities of the network under PMC and MM ∗ models. To apply our results, we give an application on the enhanced hypercube in the end and derive a lemma explaining whether these are 3-cycles in enhanced hypercubes and how many common neighbours for two vertices of enhanced hypercubes under different values of k in the meantime. [ABSTRACT FROM AUTHOR]

A binary [ n , k ] -linear code is a k -dimensional subspace of 2 n . For x ∈ 2 n , the set x + is a coset of . In this work, we study a partial ordering on the set of cosets of a binary linear code of length n : for x , y ∈ 2 n , x ≼ y provided that supp (x) ⊆ supp (y) , and we construct its associated Hasse diagram. We give general and particular examples that help to understand the concept and we obtain general properties of this graph. [ABSTRACT FROM AUTHOR]

Let k ≥ 2 be an integer. A tree T is called a k-tree if d T (v) ≤ k for each v ∈ V (T) ; that is, the maximum degree of a k-tree is at most k. A k-tree T is a spanning k-tree if T is a spanning subgraph of a connected graph G. Let λ 1 (D (G)) denote the distance spectral radius in G, where D(G) denotes the distance matrix of G. In this paper, we verify an upper bound for λ 1 (D (G)) in a connected graph G to guarantee the existence of a spanning k-tree in G. [ABSTRACT FROM AUTHOR]

A mobile agent, which is an autonomous device navigating in a graph, has to explore a given graph by visiting all of its nodes. We adopt the (arguably) weakest possible model of such a device: a deterministic memoryless automaton (DMA), i.e., a deterministic automaton with a single state. As expected, such a weak machine is incapable of exploring many graphs without marking nodes. Hence we allow the agent to use identical movable pebbles that can be dropped on nodes or picked from them. It turns out that this marking capability significantly enhances the exploration power of the agent. Our goal is to study how the availability of pebbles impacts the class of graphs that a DMA can explore. We first concentrate on finite graphs and show that any finite tree can be explored by a DMA without pebbles but there exist (small) finite graphs that cannot be explored by a DMA without pebbles. Then we turn attention to infinite graphs and fully characterize the class of infinite trees that can be explored by a DMA without pebbles. We also define a large class of infinite trees that can be explored by a DMA with finitely many pebbles. It turns out that many of these trees cannot be explored by a DMA without pebbles. On the other hand, we show a large class of infinite trees that cannot be explored by a DMA with finitely many pebbles. Thus, availability of pebbles yields a strict hierarchy of difficulty of exploration of infinite graphs by a DMA, and this hierarchy is strict even for the class of infinite trees: some trees can be explored without pebbles, some trees can be explored with finitely many pebbles but not without pebbles, and some trees require infinitely many pebbles. Finally, we consider exploration by a DMA with infinitely many pebbles. It turns out that all infinite trees can be explored by a DMA with infinitely many pebbles. By contrast, we construct infinite graphs that cannot be explored by any DMA, even with infinitely many pebbles. [ABSTRACT FROM AUTHOR]

An isolating set in a graph is a set X of vertices such that every edge of the graph is incident with a vertex of X or its neighborhood. The isolation number of a graph, or equivalently the vertex-edge domination number, is the minimum number of vertices in an isolating set. Caro and Hansberg, and independently Żyliński, showed that the isolation number is at most one-third the order for every connected graph of order at least 6. We show that in fact all such graphs have three disjoint isolating sets. Further, using a family introduced by Lemańska, Mora, and Souto-Salorio, we determine all graphs with equality in the original bound. [ABSTRACT FROM AUTHOR]

Given a pair of real symmetric matrices A , B ∈ R n × n with nonzero patterns determined by the edges of any pair of chosen graphs on n vertices, we consider an inverse eigenvalue problem for the structured matrix C = [ A B I O ] ∈ R 2 n × 2 n. We conjecture that C can attain any spectrum that is closed under conjugation. We use a structured Jacobian method to prove this conjecture for A and B of orders at most 4 or when the graph of A has a Hamilton path, and prove a weaker version of this conjecture for any pair of graphs with a restriction on the multiplicities of eigenvalues of C. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph and A (G) be the adjacency matrix of G. A diagonal matrix with diagonal entries ±1 is called a signature matrix. If A (G) is nonsingular and X = S A (G) − 1 S − 1 is entrywise nonnegative for some signature matrix S , then X can be viewed as the adjacency matrix of a unique weighted graph. It is called the inverse of G , denoted by G +. A graph G is said to have the reciprocal eigenvalue property (property(R)) if A (G) is nonsingular, and 1 λ is an eigenvalue of A (G) whenever λ is an eigenvalue of A (G). Further, if λ and 1 λ have the same multiplicity for each eigenvalue λ , then G is said to have the strong reciprocal eigenvalue property (property (SR)). It is known that for a tree T , the following conditions are equivalent: a) T + is isomorphic to T , b) T has property (R), c) T has property (SR) and d) T is a corona tree (it is a tree which is obtained from another tree by adding a new pendant at each vertex). Studies on the inverses, property (R) and property (SR) of bipartite graphs are available in the literature. However, their studies for the non-bipartite graphs are rarely done. In this article, we study the inverse and property (SR) for non-bipartite graphs. We first introduce an operation, which helps us to study the inverses of non-bipartite graphs. As a consequence, we supply a class of non-bipartite graphs for which the inverse graph G + exists and G + is isomorphic to G. It follows that each graph G in this class has property (SR). [ABSTRACT FROM AUTHOR]

The oriented chromatic number of a directed graph G is the minimum order of an oriented graph to which G has a homomorphism. The oriented chromatic number χ o (F) of a graph family F is the maximum oriented chromatic number over any orientation of any graph in F. For the family of hexagonal grids H 2 , Bielak (2006) proved that 5 ≤ χ o (H 2) ≤ 6. Here we close the gap by showing that χ o (H 2) ≥ 6. [ABSTRACT FROM AUTHOR]

With the development of artificial intelligence and deep learning technologies, image captioning has become an important research direction at the intersection of computer vision and natural language processing. The purpose of image captioning is to generate corresponding natural language descriptions by understanding the content of images. This technology has broad application prospects in fields such as image retrieval, autonomous driving, and visual question answering. Currently, many researchers have proposed region-based image captioning methods. These methods generate captions by extracting features from different regions of an image. However, they often rely on local features of the image and overlook the understanding of the overall scene, leading to captions that lack coherence and accuracy when dealing with complex scenes. Additionally, image captioning methods are unable to extract complete semantic information from visual data, which may lead to captions with biases and deficiencies. Due to these reasons, existing methods struggle to generate comprehensive and accurate captions. To fill this gap, we propose the Semantic Scenes Encoder (SSE) for image captioning. It first extracts a scene graph from the image and integrates it into the encoding of the image information. Then, it extracts a semantic graph from the captions and preserves semantic information through a learnable attention mechanism, which we refer to as the dictionary. During the generation of captions, it combines the encoded information of the image and the learned semantic information to generate complete and accurate captions. To verify the effectiveness of the SSE, we tested the model on the MSCOCO dataset. The experimental results show that the SSE improves the overall quality of the captions. The improvement in scores across multiple evaluation metrics further demonstrates that the SSE possesses significant advantages when processing identical images. [ABSTRACT FROM AUTHOR]

This paper presents three novel encryption and decryption schemes based on graph theory that aim to improve security and error resistance in communication networks. The novelty of this work lies in the application of complete bipartite graphs in two of the schemes and the Cartesian product of graphs in the third, representing a unique approach to cryptographic algorithm development. Unlike traditional cryptographic methods, these graph-based schemes use structural properties of graphs to achieve robust encryption, providing greater resistance to attacks and corruption. Each scheme is illustrated with detailed examples that show how the algorithms can be successfully implemented. The algorithms are written in standard mathematical notation, making them adaptable for machine implementation and scalable for real-world use. The schemes are also rigorously analyzed and compared in terms of their temporal and spatial complexities, using Big O notation. This comprehensive evaluation focuses on their effectiveness, providing valuable insights into their potential for secure communication in modern networks. [ABSTRACT FROM AUTHOR]

The crossing number cr(H) of a graph H is the minimum number of edge crossings over all drawings of H in the plane. Let H∗ be the connected graph of order five isomorphic to K5 ∖ e obtained by removing one edge from the complete graph K5. The main aim of the paper is to give the crossing numbers of the join products H∗ + Pn and H∗ + Cn, where Pn and Cn are the path and the cycle on n vertices, respectively. The proofs are done with the help of a suitable classification of a large number of drawings of the graph H∗ in view of the existence of a separating cycle of two possible types. [ABSTRACT FROM AUTHOR]

The correlation of the set of attributes is a crucial statistical value for the measuring of prediction potential present in a dataset. The correlation coefficient, which measures the correlation between the values of two attributes, can be used in order to measure the prediction potential between two-element subsets of a dataset containing a high number of attributes. In this way two common summary visualizations of prediction potential in datasets are formed—correlation matrices and correlation heatmaps. Both of these visualizations are focused on the presentation of correlation between pair of attributes but not much more regarding the context of correlations in the dataset. The main objective of this article is the design and implementation of graphical models usable in a visual representation of data prediction potential—correlation graphs and correlation chains—which emphasize the pseudo-transitivity of prediction potential in a dataset. [ABSTRACT FROM AUTHOR]

Let C k (n) denote the family of all connected graphs of order n with chromatic number k. In this paper we show that the conjecture proposed by Tomescu which if x ≥ k ≥ 4 and G ∈ C k (n) , then P (G , x) ≤ (x) k (x - 1) n - k holds under the additional condition that G has an independent cut-set T of size at most 2 such that the number of components in G \ T is equal to the independence number of G. [ABSTRACT FROM AUTHOR]

In metropolitan subway operations, the implementation of express train services is crucial for facilitating the efficient movement of large passenger volumes. However, preliminary feasibility studies for express train operations often rely on outdated standards from the 1990s, which fail to accurately reflect contemporary needs and conditions. To address these limitations, this study employs a Graph Convolutional Network (GCN) utilizing data from subway stations, user reviews, and the interrelationships between stations. This approach aims to provide a more current and comprehensive method for selecting express stop stations, incorporating user feedback. Additionally, the study evaluates efficiency using Data Envelopment Analysis (DEA). The findings demonstrate a significant increase in efficiency on the subway lines between Japan and New York, thereby validating the potential of using review data in the selection of express stop stations. This paper presents a novel set of criteria for effective stop selection that aligns with user needs, promoting more efficient budget allocation and broader public support. [ABSTRACT FROM AUTHOR]

Long non‐coding RNAs (lncRNAs) and microRNAs (miRNAs) are two typical types of non‐coding RNAs that interact and play important regulatory roles in many animal organisms. Exploring the unknown interactions between lncRNAs and miRNAs contributes to a better understanding of their functional involvement. Currently, studying the interactions between lncRNAs and miRNAs heavily relies on laborious biological experiments. Therefore, it is necessary to design a computational method for predicting lncRNA–miRNA interactions. In this work, we propose a method called MPGK‐LMI, which utilizes a graph attention network (GAT) to predict lncRNA–miRNA interactions in animals. First, we construct a meta‐path similarity matrix based on known lncRNA–miRNA interaction information. Then, we use GAT to aggregate the constructed meta‐path similarity matrix and the computed Gaussian kernel similarity matrix to update the feature matrix with neighbourhood information. Finally, a scoring module is used for prediction. By comparing with three state‐of‐the‐art algorithms, MPGK‐LMI achieves the best results in terms of performance, with AUC value of 0.9077, AUPR of 0.9327, ACC of 0.9080, F1‐score of 0.9143 and precision of 0.8739. These results validate the effectiveness and reliability of MPGK‐LMI. Additionally, we conduct detailed case studies to demonstrate the effectiveness and feasibility of our approach in practical applications. Through these empirical results, we gain deeper insights into the functional roles and mechanisms of lncRNA–miRNA interactions, providing significant breakthroughs and advancements in this field of research. In summary, our method not only outperforms others in terms of performance but also establishes its practicality and reliability in biological research through real‐case analysis, offering strong support and guidance for future studies and applications. [ABSTRACT FROM AUTHOR]

The relative fixity of a digraph Γ is defined as the ratio between the largest number of vertices fixed by a nontrivial automorphism of Γ and the number of vertices of Γ . We characterize the vertex-primitive digraphs whose relative fixity is at least 1 3 , and we show that there are only finitely many vertex-primitive digraphs of bounded out-valency and relative fixity exceeding a positive constant. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with vertex set V(G) (|V(G)| = n) and let S ⊆ V(G). We denote by d¡, the degree of the vertex vi. The graph GS is obtained from G by removing all the vertices belonging to S (If S = {vj}, then GS is denoted by G(j)). The energy of G is the sum of all absolute values of the eigenvalues of the adjacency matrix A(G) and is denoted by ε (G). Recently, Espinal and Rada (MATCH Commun Math Comput Chem 92(1):89-103, 2024) introduced the concept of local energy of a graph e(G). It is defined as e(G) = Σj=in εG(vj), where εG(vj) = ε (G) -- ε(G(j)) is called the local energy of a graph G at vertex vj. In this paper, we prove that if v1 ∈ S and S is a vertex independent set of size k such that every vertex in S share the same open neighborhood set NG (v1), then ε (G) -- ε (GS) ≤ 2 √k d1. We also characterize graphs that satisfy the equality case. If S = {v1}, we get ε (G) -- ε (G(1)) ≤ 2 √d1 Espinal and Rada (MATCH Commun Math Comput Chem 92(1):89-103, 2024). One of the open problems in the study of local energy of a graph is to characterize graphs with e(G) = 2ε(G). Motivated by this problem, we present an infinite class of graphs for which e(G) < 2ε(G). As a result, we show that for a complete multipartite graph G, e(G) = 2ε (G) if and only if G ≅ K2. We also prove that the local energy of a complete multipartite graph G is constant at each vertex of the graph if and only if G is regular. Finally, we give an upper bound on e(G) in terms of n and chromatic number k. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new graph polynomial, say connectivity polynomial. Let G be a simple graph of order n. The connectivity polynomial of G, denoted by 풞(G,x), is 풞(G,x) =∑i=0nc ixi, where c0 = 1 and ci (for i ≥ 1) is the number of connected induced subgraphs of G with order i. We investigate some properties of the connectivity polynomial. We find the connectivity polynomial of disjoint union and join of graphs. Finally, we find the coefficients of this polynomial in terms of the vertex connectivity and the order of graphs. [ABSTRACT FROM AUTHOR]

In this paper, we study a new graph structure, called the directsumgraph on a finite-dimensional vector space. We investigate the connectivity, diameter and the completeness of ΓU⊕W(핍). We also determine the degree of each vertex in case the base field is finite. We establish some results about Eulerian and triangulation of the graph ΓU⊕W(핍). Finally, we find the domination number and independence number, size, girth, edge-connectivity, clique number and the chromatic number of ΓU⊕W(핍). [ABSTRACT FROM AUTHOR]

Emotion is a complex state caused by the functioning of the human brain in relation to various events, for which there is no scientific definition. Emotion recognition is traditionally conducted by psychologists and experts based on facial expressions—the traditional way to recognize something limited and is associated with errors. This study presents a new automatic method using electroencephalogram (EEG) signals based on combining graph theory with convolutional networks for emotion recognition. In the proposed model, firstly, a comprehensive database based on musical stimuli is provided to induce two and three emotional classes, including positive, negative, and neutral emotions. Generative adversarial networks (GANs) are used to supplement the recorded data, which are then input into the suggested deep network for feature extraction and classification. The suggested deep network can extract the dynamic information from the EEG data in an optimal manner and has 4 GConv layers. The accuracy of the categorization for two classes and three classes, respectively, is 99% and 98%, according to the suggested strategy. The suggested model has been compared with recent research and algorithms and has provided promising results. The proposed method can be used to complete the brain-computer-interface (BCI) systems puzzle. [ABSTRACT FROM AUTHOR]

Background: Applying graph convolutional networks (GCN) to the classification of free-form natural language texts leveraged by graph-of-words features (TextGCN) was studied and confirmed to be an effective means of describing complex natural language texts. However, the text classification models based on the TextGCN possess weaknesses in terms of memory consumption and model dissemination and distribution. In this paper, we present a fast message passing network (FastMPN), implementing a GCN with message passing architecture that provides versatility and flexibility by allowing trainable node embedding and edge weights, helping the GCN model find the better solution. We applied the FastMPN model to the task of clinical information extraction from cancer pathology reports, extracting the following six properties: main site, subsite, laterality, histology, behavior, and grade. Results: We evaluated the clinical task performance of the FastMPN models in terms of micro- and macro-averaged F1 scores. A comparison was performed with the multi-task convolutional neural network (MT-CNN) model. Results show that the FastMPN model is equivalent to or better than the MT-CNN. Conclusions: Our implementation revealed that our FastMPN model, which is based on the PyTorch platform, can train a large corpus (667,290 training samples) with 202,373 unique words in less than 3 minutes per epoch using one NVIDIA V100 hardware accelerator. Our experiments demonstrated that using this implementation, the clinical task performance scores of information extraction related to tumors from cancer pathology reports were highly competitive. [ABSTRACT FROM AUTHOR]

Assume there exists a function h : E (G) → [ 0 , 1 ] such that g (x) ≤ ∑ e ∈ E (G) , x ∋ e h (e) ≤ f (x) for every vertex x of G. The spanning subgraph of G induced by the set of edges { e ∈ E (G) : h (e) > 0 } is called a fractional (g , f) -factor of G with indicator function h. Let M and N be two disjoint sets of independent edges of G satisfying | M | = m and | N | = n. We say that G possesses a fractional (g , f) -factor with the property E (m , n) if G contains a fractional (g , f) -factor with indicator function h such that h (e) = 1 for each e ∈ M and h (e) = 0 for each e ∈ N. In this article, we discuss stability number and minimum degree conditions for graphs to possess fractional (g , f) -factors with the property E (1 , n). Furthermore, we explain that the stability number and minimum degree conditions declared in the main result are sharp. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with identity and I be an ideal of R. The zero-divisor graph of R with respect to I, denoted by ΓI(R), is the graph whose vertices are the set {x ∈ R∖I|xy ∈ I for some y ∈ R∖I} with distinct vertices x and y are adjacent if and only if xy ∈ I. The cozero-divisor graph Γ′(R) of R is the graph whose vertices are precisely the non-zero, non-unit elements of R and two distinct vertices x and y are adjacent if and only if x∉yR and y∉xR. In this paper, we introduced and investigated a new generalization of the cozero-divisor graph Γ′(R) of R denoted by ΓI″(R). In fact, ΓI″(R) is a dual notion of ΓI(R). [ABSTRACT FROM AUTHOR]

In this article, we generalize the perfect neighborhood number of a graph G = (V, E) as a k - perfect neighborhood number ηkp(G). Here many bounds and exact values of some specific family of graphs are obtained. Also, its relationship with other graph theoretic parameters are investigated. [ABSTRACT FROM AUTHOR]

In this paper, we present a method for finding the absorbing radical of a finite-dimensional evolution algebra. Such a method consists of finding the acyclic vertices of an oriented graph associated with the algebra. The set of generators associated with such vertices turn out to be the generators of the absorption radical. As an application we use the absorption radical to study the decomposability of some degenerate evolution algebras. [ABSTRACT FROM AUTHOR]

The increasingly widespread use of new power equipment has brought new disturbances to the power system and has placed increasing demands on power quality. In order to make full use of the power quality indicators in the national standards and to make a more comprehensive and integrated evaluation of power quality, this study proposes a power quality evaluation method based on graph convolutional network. A power quality assessment system with graded indicators is proposed according to the current national standards. The correlation between the various power quality assessment indicators is initially determined, and on this basis the indicator relationship diagram is determined, a graph neural network model is built and trained, and the error rate of the test set is 9.02%. A comparison and analysis with other assessment methods using actual measurement data of a power system proves that the proposed method is more effective in assessing power quality over a long time span. [ABSTRACT FROM AUTHOR]

Moran's I is a spatial autocorrelation measure of univariate spatial data. Therefore, even if p spatial data exist, we can only obtain p values for Moran's I. In other words, Moran's I cannot measure the degree of spatial autocorrelation of multivariate spatial data as a single value. This paper addresses this issue. That is, we extend Moran's I so that it can measure the degree of spatial autocorrelation of multivariate spatial data as a single value. In addition, since the local version of Moran's I has the same problem, we extend it as well. Then, we establish their properties, which are fundamental for applied work. Numerical illustrations of the theoretical results obtained in the paper are also provided. [ABSTRACT FROM AUTHOR]

Graph analytics attract much attention from both research and industry communities. Due to its linear time complexity, the k-core decomposition is widely used in many real-world applications such as biology, social networks, community detection, ecology, and information spreading. In many such applications, the data graphs continuously change over time. The changes correspond to edge insertion and removal. Instead of recomputing the k-core, which is time-consuming, we study how to maintain the k-core efficiently. That is, when inserting or deleting an edge, we need to identify the affected vertices by searching for more vertices. The state-of-the-art order-based method maintains an order, the so-called k-order, among all vertices, which can significantly reduce the searching space. However, this order-based method is complicated to understand and implement, and its correctness is not formally discussed. In this work, we propose a simplified order-based approach by introducing the classical Order Data Structure to maintain the k-order, which significantly improves the worst-case time complexity for both edge insertion and removal algorithms. Also, our simplified method is intuitive to understand and implement; it is easy to argue the correctness formally. Additionally, we discuss a simplified batch insertion approach. The experiments evaluate our simplified method over 12 real and synthetic graphs with billions of vertices. Compared with the existing method, our simplified approach achieves high speedups up to 7.7× and 9.7× for edge insertion and removal, respectively. [ABSTRACT FROM AUTHOR]

Unmanned Aerial Vehicles (UAVs) play a very important role in military and civilian activities. In this paper, the aim is to cover the borders of Iran using UAVs. For this purpose, two zero-one programming models are presented. In the first model, our goal is to cover the borders of Iran at the minimum total time (the required time to prepare UAVs to start flying and the flight time of the UAVs). In this model, by minimizing the total time of UAVs for covering the borders, the costs appropriate to the flight of UAVs (such as the fuel costs of UAVs) are also reduced. In the second model, which is mostly used in emergencies and when a military attack occurs on the country’s borders, the aim is to minimize the maximum required time to counter attacks and cover the entire country’s borders. The efficiency of both models is shown by numerical examples. [ABSTRACT FROM AUTHOR]

The integrity of a graph G is defined as the minimum value of | S | + m (G − S) taken over all S ⊆ V (G) , where m (H) denotes the maximum cardinality of a component of graph H. In this paper, we investigate bounds on the maximum and minimum values of the weighted version of this parameter. We also consider the same question for the related parameter vertex-neighbor-integrity. [ABSTRACT FROM AUTHOR]

We prove that if each edge of a graph G $G$ belongs to at least seven triangles, then G $G$ contains a K9 ${K}_{9}$‐minor or contains K1,2,2,2,2,2 ${K}_{1,2,2,2,2,2}$ as an induced subgraph. This result was conjectured by Albar and Gonçalves in 2018. Moreover, we apply this result to study the stress freeness of graphs. [ABSTRACT FROM AUTHOR]

For a set 풜 of connected graphs, an 풜-factor is a spanning subgraph of a graph, whose connected components are isomorphic to graphs from the set 풜. An 풜-factor is also referred as a component factor. A graph G is called an (풜, m)-factor deleted graph if for every E′⊆E(G) with |E′| = m, G−E′ admits an 풜-factor. A graph G is called an (풜, l)-factor critical graph if for every V′⊆V (G) with |V′| = l, G−V′ admits an 풜-factor. Let m, l and k be three positive integers with k ≥ 2, and write ℱ = {P2, C3, P5, 풯 (3)} and ℋ = {K1,1, K1,2,... , K1,k, 풯 (2k + 1)}, where 풯 (3) and 풯 (2k + 1) are two special families of trees. Inspired by finding a sufficient condition to check for the existence of path-factors with some special restraints, we focus on the sufficient conditions based on a graphic parameter called degree sum: σκ(G) = min⁡X⊆V(G) {Σx∈XdG(x):X is an independent set of k vertices}. σκ(G) = min⁡X⊆V(G) {Σx∈XdG(x):X is an independent set of k vertices}. σ κ (G) = min ⁡ X ⊆ V (G) { Σ x ∈ X d G (x) : X is an independent set of k vertices }. In this article, we verify that: (i) an (l + 2)-connected graph G of order n is an (ℱ, l)-factor critical graph if σ3(G) ≥ 6n+9l/5 σ3(G)≥6n+9l5 σ 3 (G) ≥ 6 n + 9 l 5 ; (ii) a (2m + 1)-connected graph G of order n is an (ℱ, m)-factor deleted graph if σm+2(G) ≥ 6/5n σm+2(G)≥65n σ m + 2 (G) ≥ 6 5 n ; (iii) an (l + 2)-connected graph G of order n is an (ℋ, l)-factor critical graph if σ2k+1(G) ≥ 6n+(6k+3)l/2k+3 σ2k+1(G)≥6n+(6k+3)l2k+3 σ 2 k + 1 (G) ≥ 6 n + (6 k + 3) l 2 k + 3 ; (iv) a (2m + 1)-connected graph G of order n is an (ℋ, m)-factor deleted graph if σm+2(G) ≥ 6n/2k+3 σm+2(G)≥6n2k+3 σ m + 2 (G) ≥ 6 n 2 k + 3 . [ABSTRACT FROM AUTHOR]

In a partition-graph restricted cooperative game with incomplete information, it is assumed that a prior coalition takes part in the grand coalition N in form of communication structure. Before the grand coalition is formed, all the players participate in the cooperation just by communication structure. Hence, a new cooperative game with communication structure (a restricted game for short) is formed. In this study, a new value of a restricted game is proposed, which is defined by the Myserson value and the Shapley value. It is proved that the added value of grand coalition is distributed by a certain ratio (i.e., the Shapley value). By generalized the distribution ratio, a further extension of the proposed value is gotten, i.e., the weight extended value. This weight extended value is unique based on restricted component efficiency, weight fairness, weight symmetric across coalitions, null coalition property and restricted linearity. [ABSTRACT FROM AUTHOR]

Tracing a student's knowledge state is critical for teaching and learning. Knowledge tracing aims to accurately predict student performance by analyzing historical records on online education platforms. Most studies have focused on a student's skill with interactions sequence to predict the probability of correctly answering the latest question. However, they still suffer from the challenge of information sparsity and student forgetting. Specifically, the relationship between question and skill, and the features related to question texts have not been integrated to enrich information exploration. Besides, modeling forgetting behavior remains a challenge in assessing a student's learning gains. In this paper, we present a novel model, namely Informative Representations for Forgetting-Robust Knowledge Tracing (IFKT). IFKT utilizes a light graph convolutional network to capture various relational structures via embedding propagation. Then, the embeddings are assembled with rich interaction features separately as the powerful representation. Furthermore, attention weights assignments are individualized using the relative positions, in addition to the relevance between the current question with historical interaction representations. Finally, we compare IFKT against seven knowledge tracing baselines on three real-world benchmark datasets, demonstrating the superiority of the proposed model. [ABSTRACT FROM AUTHOR]

Let X = { X (t) , t ∈ R N } be a centered space-time anisotropic Gaussian random field in R d with stationary increments, where the components X i (i = 1 , ... , d) are independent but distributed differently. Under certain conditions, we not only give the Hausdorff dimension of the graph sets of X in the asymmetric metric in the recurrent case, but also determine the exact Hausdorff measure functions of the graph sets of X in the transient and recurrent cases, respectively. Moreover, we establish a uniform Hausdorff dimension result for the image sets of X. Our results extend the corresponding results on fractional Brownian motion and space or time anisotropic Gaussian random fields. [ABSTRACT FROM AUTHOR]

Butterfly (a cyclic graph motif) counting is a fundamental task with many applications in graph analysis, which aims at computing the number of butterflies in a large graph. With the rapid growth of graph data, it is more and more challenging to do butterfly counting due to the super-linear time complexity and large memory consumption. In this paper, we study I/O-efficient algorithms for doing butterfly counting on hierarchical memory. Existing algorithms of this kind cannot guarantee I/O optimality. Observing that in order to count butterflies, it suffices to "witness" a subgraph instead of the whole structure, a new class of algorithms called semi-witnessing algorithm is proposed. We prove that a semi-witnessing algorithm is not restricted by the lower bound Ω ( | E | 2 MB) of a witnessing algorithm, and give a new bound of Ω (min ( | E | 2 MB , | E | | V | M B)) . Subsequently, we develop the IOBufs algorithm that manages to approach the I/O lower bound, and thus claim its optimality. Finally, we investigate the parallelization of IOBufs to improve its performance and scalability. To support various hardware configurations, we introduce a general parallel framework, PIOBufs . Our analysis indicates that the key to implementing PIOBufs on multi-core CPUs lies in the fine-grained task division. Furthermore, we extend the CPU-tailored PIOBufs to harness the extensive parallelism that GPUs provide. Our experimental results show that IOBufs performs better than established algorithms such as EMRC , BFC - EM and G - BFC . Thanks to its I/O-efficient design, IOBufs can handle large graphs that exceed the main memory capacity on both CPUs and GPUs. A significant result is that IOBufs can manage butterfly counting on the Clueweb graph, which has 37 billion edges and quintillions ( 10 18 ) of butterflies. [ABSTRACT FROM AUTHOR]

Abstract Improved ability to assess and categorize the spatial characteristics of settlement patterns is required for a deeper understanding of how urbanization is driving land use and land cover transformation and its effects. Two approaches to the globally available settlement maps of the World Settlement Footprint 3D support a detailed assessment of spatial characteristics of settlement patterns in rural to urban landscapes and across scales: graph-based spatial network analysis and elements of fractal theory. Based on first comprehensive tests for the Punjab (India), the Nile Delta (Egypt) and the North China Plain, the results of our study suggest that the presented methods allow a quantitative and qualitative characterization and comparison of settlement patterns between different regions of the world. The approache allows to generate standardized baseline data for arbitrary regions in the world to analyze structuring principles of settlement hierarchies (e.g., self-organized fractal geometries) and their dependence on - or interaction with - cultural, political, socioeconomic, or environmental conditions.

Abstract Background Applying graph convolutional networks (GCN) to the classification of free-form natural language texts leveraged by graph-of-words features (TextGCN) was studied and confirmed to be an effective means of describing complex natural language texts. However, the text classification models based on the TextGCN possess weaknesses in terms of memory consumption and model dissemination and distribution. In this paper, we present a fast message passing network (FastMPN), implementing a GCN with message passing architecture that provides versatility and flexibility by allowing trainable node embedding and edge weights, helping the GCN model find the better solution. We applied the FastMPN model to the task of clinical information extraction from cancer pathology reports, extracting the following six properties: main site, subsite, laterality, histology, behavior, and grade. Results We evaluated the clinical task performance of the FastMPN models in terms of micro- and macro-averaged F1 scores. A comparison was performed with the multi-task convolutional neural network (MT-CNN) model. Results show that the FastMPN model is equivalent to or better than the MT-CNN. Conclusions Our implementation revealed that our FastMPN model, which is based on the PyTorch platform, can train a large corpus (667,290 training samples) with 202,373 unique words in less than 3 minutes per epoch using one NVIDIA V100 hardware accelerator. Our experiments demonstrated that using this implementation, the clinical task performance scores of information extraction related to tumors from cancer pathology reports were highly competitive.

This article presents the notions of extended b-gauge space (U,Qφ;Ω)\left(U,{Q}_{\varphi ;\Omega }) and extended Jφ;Ω{{\mathcal{J}}}_{\varphi ;\Omega }-families of generalized extended pseudo-b-distances on UU. Furthermore, we look at these extended Jφ;Ω{{\mathcal{J}}}_{\varphi ;\Omega }-families on UU and define the extended Jφ;Ω{{\mathcal{J}}}_{\varphi ;\Omega }-sequential completeness. We also look into some fixed and periodic point theorems for set-valued mappings in the new space with a graph that does not meet the completeness condition of the space. Additionally, this article includes some examples to explain the corresponding results and highlights some important consequences of our obtained results.

Abstract Quantitative structure relationships linked to a chemical structure that shed light on its properties and chemical reactions are called topological indices. This structure is upset by the addition of silicon (Si) doping, which changes the electrical and optical characteristics. In this article, we examine the connection between a chemical structure’s Gibbs energy (GE) and K-Banhatti indices. In this article, we compute the K-Banhatti indices and then show the correlation between the indices and Gibb’s energy of the molecule using curve fitting. Through the curve fitting, we see that there is a strong correlation between indices and Gibb’s energy of a molecule. We use the polynomial curve fitting approach to see the correlation between indices and Gibb’s energy.

In recent years, significant progress has been made in video-based person re-identification (Re-ID). The key challenge in video person Re-ID lies in effectively constructing discriminative and robust person feature representations. Methods based on local regions utilize spatial and temporal attention to extract representative local features. However, prior approaches often overlook the correlations between local regions. To leverage relationships among different local regions, we have proposed a novel video person Re-ID representation learning approach based on a graph transformer, which facilitates contextual interactions between relevant region features. Specifically, we construct a local relation graph to model intrinsic relationships between nodes representing local regions. This graph employs the architecture of a transformer for feature propagation, iteratively refining region features and considering information from adjacent nodes to obtain partial feature representations. To learn compact and discriminative representations, we have further proposed a global feature learning branch based on a vision transformer to capture the relationships between different frames in a sequence. Additionally, we designed a dual-branch interaction network based on multi-head fusion attention to integrate frame-level features extracted by both local and global branches. Finally, the concatenated global and local features, after interaction, are used for testing. We evaluated the proposed method on three datasets, namely iLIDS-VID, MARS, and DukeMTMC-VideoReID. Experimental results demonstrate competitive performance, validating the effectiveness of our proposed approach.

The research is devoted to the estimation the structural complexity of programs. The algorithm of finding cyclomatic routes for program executions is described. By now, two directions of obtaining estimates for the complexity estimates in software modules have been defined: structural and statistical. Both directions connect the value of program complexity with the labor intensity related to their development. The structural complexity of program modules is determined by the number of interacting components, the number and complexity of links between them. The complexity of a program's behavior depends to a large extent on the set of routes through which it is executed. The complexity metric obtained from these positions allows us to determine estimates of the cost of designing the program as a whole, as well as to identify the modules that are likely to contain the most errors, especially the logical ones.

Purpose. Ensuring the safety of train traffic is a mandatory task in the development of technical equipment of railway transport in Ukraine. To diagnose and verify the performance of such systems, simulation models of overhead devices, in particular, the rail circle, are used. The most commonly used models are in the form of differential equations and in operator form. Unfortunately, they are not fully suitable for solving this problem. In this regard, there is a need to create a mathematical model that is easier to integrate for checking both relay electrical interlocking and microprocessor-based interlocking systems. Methodology. To achieve this goal, the authors proposed to create a mathematical model in the form of a finite discrete automaton. This paper considers the creation of a model of a station rail circuit as a directed graph. During the creation of the model, the input and output values of the model and the states are determined. The tables of inputs and outputs of the automaton are constructed, sequential expressions for the abstract model of the automaton are created, and their minimization is performed. The states of the automaton are coded using trigger circuits. Findings. In the course of the research, a mathematical model of the rail circle in the form of a Moore model finite automaton was created, and its performance was tested in the Proteus software environment. The developed model allows to simulate the operation of a stationary rail circuit at the level of abstraction, which operates with binary signals. This makes it possible to simplify the coordination of the model with microprocessor-based centralization software. In general, it is now possible to more effectively check the performance of microprocessor-based interlocking systems at the design and commissioning stages. Originality. The developed mathematical model makes it possible to determine the response of the microprocessor-based centralization software to the behavior of the rail circuit in various, in particular atypical, operating modes, as well as to determine the response of the station electrical centralization system to individual failures and to the occurrence of several failures simultaneously. Practical value. The proposed mathematical model can be used both to check the operation of microprocessor-based centralization systems at the design and implementation stages and for relay centralization systems when developing diagnostic complexes for monitoring their performance.

In crisp graph theory, there are numerous topological indices accessible, including the Misbalance Prodeg Index, which is one of the most well-known degree-based topological indexes. In crisp graphs, both vertices and edges have membership values of $ 1 $ or $ 0 $, whereas in fuzzy graphs, both vertices and edges have different memberships. This is an entire contrast to the crisp graph. In this paper, we introduce the Fuzzy Misbalance Prodeg Index of a fuzzy graph, which is a generalized form of the Misbalance Prodeg Index of a graph. We find bounds of this index and find bounds of certain classes of graphs such as path graph, cycle graph, complete graph, complete bipartite graph, and star graph. We give an algorithm to find the Fuzzy Misbalance Prodeg Index of a graph for the model of multi-criteria decision-making is established. We present applications from daily life in multi-criteria decision-making. We apply our obtained model of the Fuzzy Misbalance Prodeg Index for the multi-criteria decision-making to the choice of the best supplier and we also show the graphical analysis of our index with the other indices that show how our index is better than other existing indices.

A graph G is a fractional (a,b,m)-deleted graph if deleting any m edges from G, the resulting subgraph still admits a fractional [a,b]-factor. As an exclusive graph-based parameter, isolated toughness and its variant are utilized to measure the vulnerability of networks which are modelled by graph topology structures. Early studies have shown the inherent connection between isolated toughness and the existence of fractional factors in specific settings. This paper provides a theoretical perspective on the sufficient conditions for fractional (a,b,m)-deleted graphs with respect to isolated toughness and its variant. The sharpness of the given isolated toughness bounds is explained by counterexamples. [ABSTRACT FROM AUTHOR]

Consider a finite directed graph without cycles in which the arrows are weighted by positive weights. We present an algorithm for the computation of a new distance, called path-length-weighted distance, which has proven useful for graph analysis in the context of fraud detection. The idea is that the new distance explicitly takes into account the size of the paths in the calculations. It has the distinct characteristic that, when calculated along the same path, it may result in a shorter distance between far-apart vertices than between adjacent ones. This property can be particularly useful for modeling scenarios where the connections between vertices are obscured by numerous intermediate vertices, such as in cases of financial fraud. For example, to hide dirty money from financial authorities, fraudsters often use multiple institutions, banks, and intermediaries between the source of the money and its final recipient. Our distance would serve to make such situations explicit. Thus, although our algorithm is based on arguments similar to those at work for the Bellman–Ford and Dijkstra methods, it is in fact essentially different, since the calculation formula contains a weight that explicitly depends on the number of intermediate vertices. This fact totally conditions the algorithm, because longer paths could provide shorter distances—contrary to the classical algorithms mentioned above. We lay out the appropriate framework for its computation, showing the constraints and requirements for its use, along with some illustrative examples. [ABSTRACT FROM AUTHOR]

Adolescent development of human brain structural and functional networks is increasingly recognized as fundamental to emergence of typical and atypical adult cognitive and emotional processes. We analysed multimodal magnetic resonance imaging (MRI) data collected from N ~ 300 healthy adolescents (51%; female; 14 to 26 y) each scanned repeatedly in an accelerated longitudinal design, to provide an analyzable dataset of 469 structural scans and 448 functional MRI scans. We estimated the morphometric similarity between each possible pair of 358 cortical areas on a feature vector comprising six macro- and microstructural MRI metrics, resulting in a morphometric similarity network (MSN) for each scan. Over the course of adolescence, we found that morphometric similarity increased in paralimbic cortical areas, e.g., insula and cingulate cortex, but generally decreased in neocortical areas, and these results were replicated in an independent developmental MRI cohort (N~304). Increasing hubness of paralimbic nodes in MSNs was associated with increased strength of coupling between their morphometric similarity and functional connectivity. Decreasing hubness of neocortical nodes in MSNs was associated with reduced strength of structure-function coupling and increasingly diverse functional connections in the corresponding fMRI networks. Neocortical areas became more structurally differentiated and more functionally integrative in a metabolically expensive process linked to cortical thinning and myelination, whereas paralimbic areas specialized for affective and interoceptive functions became less differentiated, as hypothetically predicted by a developmental transition from periallocortical to proisocortical organization of the cortex. Cytoarchitectonically distinct zones of the human cortex undergo distinct neurodevelopmental programs during typical adolescence. [ABSTRACT FROM AUTHOR]

We study the lower central series of the right-angled Coxeter group and the corresponding associated graded Lie algebra and describe the basis of the fourth graded component of for any . [ABSTRACT FROM AUTHOR]