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.

We consider the problem of finding an accurate representation of neuron shapes, extracting sub-cellular features, and classifying neurons based on neuron shapes. In neuroscience research, the skeleton representation is often used as a compact and abstract representation of neuron shapes. However, existing methods are limited to getting and analyzing curve skeletons which can only be applied for tubular shapes. This paper presents a 3D neuron morphology analysis method for more general and complex neuron shapes. First, we introduce the concept of skeleton mesh to represent general neuron shapes and propose a novel method for computing mesh representations from 3D surface point clouds. A skeleton graph is then obtained from skeleton mesh and is used to extract sub-cellular features. Finally, an unsupervised learning method is used to embed the skeleton graph for neuron classification. Extensive experiment results are provided and demonstrate the robustness of our method to analyze neuron morphology.

We introduce and study an infinite family of graceful graphs, which we call kites. The kites are graphs where a path is joined with a graph "forming" a kite. We study and characterize three classes of the kites: kites formed by cycles known to be graceful, fan kites and lantern kites. Beside showing in a transparent way that all these graphs are graceful, we provide characterizations of these graphs among all simple graphs via three tools: via Sheppard's labelling sequences introduced in the 1970s and via labelling relations and graph chessboards. The latter are relatively new tools for the study of graceful graphs introduced by Haviar and Iva\v ska in 2015. The labelling relations are closely related to Sheppard's labelling sequences while the graph chessboards provide a~nice visualization of the graceful labellings.

Accurately predicting molecular properties is a challenging but essential task in drug discovery. Recently, many mono-modal deep learning methods have been successfully applied to molecular property prediction. However, mono-modal learning is inherently limited as it relies solely on a single modality of molecular representation, which restricts a comprehensive understanding of drug molecules. To overcome the limitations, we propose a multimodal fused deep learning (MMFDL) model to leverage information from different molecular representations. Specifically, we construct a triple-modal learning model by employing Transformer-Encoder, Bidirectional Gated Recurrent Unit (BiGRU), and graph convolutional network (GCN) to process three modalities of information from chemical language and molecular graph: SMILES-encoded vectors, ECFP fingerprints, and molecular graphs, respectively. We evaluate the proposed triple-modal model using five fusion approaches on six molecule datasets, including Delaney, Llinas2020, Lipophilicity, SAMPL, BACE, and pKa from DataWarrior. The results show that the MMFDL model achieves the highest Pearson coefficients, and stable distribution of Pearson coefficients in the random splitting test, outperforming mono-modal models in accuracy and reliability. Furthermore, we validate the generalization ability of our model in the prediction of binding constants for protein-ligand complex molecules, and assess the resilience capability against noise. Through analysis of feature distributions in chemical space and the assigned contribution of each modal model, we demonstrate that the MMFDL model shows the ability to acquire complementary information by using proper models and suitable fusion approaches. By leveraging diverse sources of bioinformatics information, multimodal deep learning models hold the potential for successful drug discovery.

We consider a variation of the Cops and Robbers game in which the cops do not have perfect information; the information they receive regarding the robber's position is delayed by one round. Our parameter of interest is the time-delayed cop number of a graph G , the minimum number of cops that suffice to guarantee a win on G. We present a variety of results on this parameter, including general bounds, and make comparisons to the cop numbers of known related variants of the original game. We have particular interest in graph products, Meyniel-type bounds, and cop density. [ABSTRACT FROM AUTHOR]