Dynamic Multi-Graph Spatio-Temporal Graph Traffic Flow Prediction in Bangkok:An Application of a Continuous Convolutional Neural Network

The ability to accurately predict urban traffic flows is crucial for optimising city operations.Consequently,various methods for forecasting urban traffic have been developed,focusing on analysing historical data to understand complex mobility patterns.Deep learning techniques,such as graph neural networks(GNNs),are popular for their ability to capture spatio-temporal dependencies.However,these models often become overly complex due to the large number of hyper-parameters involved.In this study,we introduce Dynamic Multi-Graph Spatial-Temporal Graph Neural Ordinary Differential Equation Networks(DMST-GNODE),a framework based on ordinary differential equations(ODEs)that autonomously discovers effective spatial-temporal graph neural network(STGNN)architectures for traffic prediction tasks.The comparative analysis of DMST-GNODE and baseline models indicates that DMST-GNODE model demonstrates superior performance across multiple datasets,consistently achieving the lowest Root Mean Square Error(RMSE)and Mean Absolute Error(MAE)values,alongside the highest accuracy.On the BKK(Bangkok)dataset,it outperformed other models with an RMSE of 3.3165 and an accuracy of 0.9367 for a 20-min interval,maintaining this trend across 40 and 60 min.Similarly,on the PeMS08 dataset,DMST-GNODE achieved the best performance with an RMSE of 19.4863 and an accuracy of 0.9377 at 20 min,demonstrating its effectiveness over longer periods.The Los_Loop dataset results further emphasise this model’s advantage,with an RMSE of 3.3422 and an accuracy of 0.7643 at 20 min,consistently maintaining superiority across all time intervals.These numerical highlights indicate that DMST-GNODE not only outperforms baseline models but also achieves higher accuracy and lower errors across different time intervals and datasets.

GraphSTGAN:Situation understanding network of slow-fast high maneuvering targets for maritime monitor services of IoT data

With the rapid growth of the maritime Internet of Things(IoT)devices for Maritime Monitor Services(MMS),maritime traffic controllers could not handle a massive amount of data in time.For unmanned MMS,one of the key technologies is situation understanding.However,the presence of slow-fast high maneuvering targets and track breakages due to radar blind zones make modeling the dynamics of marine multi-agents difficult,and pose significant challenges to maritime situation understanding.In order to comprehend the situation accurately and thus offer unmanned MMS,it is crucial to model the complex dynamics of multi-agents using IoT big data.Nevertheless,previous methods typically rely on complex assumptions,are plagued by unstructured data,and disregard the interactions between multiple agents and the spatial-temporal correlations.A deep learning model,Graph Spatial-Temporal Generative Adversarial Network(GraphSTGAN),is proposed in this paper,which uses graph neural network to model unstructured data and uses STGAN to learn the spatial-temporal dependencies and interactions.Extensive experiments show the effectiveness and robustness of the proposed method.

Perfect 1-k Matchings of Bipartite Graphs

Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.

Algorithm for Visualization of Zero Divisor Graphs of the Ring ℤn Using MAPLE Coding

This research investigates the comparative efficacy of generating zero divisor graphs (ZDGs) of the ring of integers ℤn modulo n using MAPLE algorithm. Zero divisor graphs, pivotal in the study of ring theory, depict relationships between elements of a ring that multiply to zero. The paper explores the development and implementation of algorithms in MAPLE for constructing these ZDGs. The comparative study aims to discern the strengths, limitations, and computational efficiency of different MAPLE algorithms for creating zero divisor graphs offering insights for mathematicians, researchers, and computational enthusiasts involved in ring theory and mathematical computations.

Maximal Resonance of{(3,4),4}-Fullerene Graphs

A{(3,4),4}-fullerene graph S is a 4-regular map on the sphere whose faces are of length 3 or 4.It follows from Euler s formula that the number of triangular faces is eight.A set H of disjoint quadrangular faces of S is called resonant pattern if S has a perfect matching M such that every quadrangular face in H is M-alternating.Let k be a positive integer,S is k-resonant if any i≤k disjoint quadrangular faces of S form a resonant pattern.Moreover,if graph S is k-resonant for any integer k,then S is called maximally resonant.In this paper,we show that the maximally resonant{(3,4),4}-fullerene graphs are S_6,S_8,S_(10)^(2),S_(12)^(2),S_(12)^(4),S_(12)^(5),S_(14)^(3),S_(14)^(5),S_(16)^(3),S_(18)^(5),S_(24)as shown in Fig.1.As a corollary,it is shown that if a{(3,4),4}-fullerene graph is 4-resonant,then it is also maximally resonant.

Independence Polynomials and the Merrifield-Simmons Index of Mono-Layer Cylindrical Grid Graphs

Research on the independence polynomial of graphs has been very active.However,the computational complexity of determining independence polynomials for general graphs remains NP-hard.Letα(G)be the independence number of G and i(G;k)be the number of independent sets of order k in G,then the independence polynomial is defined as I(G;x)=∑_(k=0)^(α(G))i(G;k)x^(k),i(G;0)=1.In this paper,by utilizing the transfer matrix,we obtain an analytical expression for I(CGn;x)of mono-cylindrical grid graphs CGn and present a crucial proof of it.Moreover,we also explore the Merrifield-Simmons index and other properties of CGn.

On an Invariant of Tournament Digraphs

To date, it is unknown whether it is possible to construct a complete graph invariant in polynomial time, so fast algorithms for checking non-isomorphism are important, including heuristic algorithms, and for successful implementations of such heuristics, both the tasks of some modification of previously described graph invariants and the description of new invariants remain relevant. Many of the described invariants make it possible to distinguish a larger number of graphs in the real time of a computer program. In this paper, we propose an invariant for a special kind of directed graphs, namely, for tournaments. The last ones, from our point of view, are interesting because when fixing the order of vertices, the number of different tournaments is exactly equal to the number of undirected graphs, also with fixing the order of vertices. In the invariant we are considering, all possible tournaments consisting of a subset of vertices of a given digraph with the same set of arcs are iterated over. For such subset tournaments, the places are calculated in the usual way, which are summed up to obtain the final values of the points of the vertices;these points form the proposed invariant. As we expected, calculations of the new invariant showed that it does not coincide with the most natural invariant for tournaments, in which the number of points is calculated for each participant. So far, we have conducted a small number of computational experiments, and the minimum value of the pair correlation between the sequences representing these two invariants that we found is for dimension 15.

Weak External Bisection of Some Graphs

Let G be a graph. A bipartition of G is a bipartition of V (G) with V (G) = V1 ∪ V2 and V1 ∩ V2 = ∅. If a bipartition satisfies ∥V1∣ - ∣V2∥ ≤ 1, we call it a bisection. The research in this paper is mainly based on a conjecture proposed by Bollobás and Scott. The conjecture is that every graph G has a bisection (V1, V2) such that ∀v ∈ V1, at least half minuses one of the neighbors of v are in the V2;∀v ∈ V2, at least half minuses one of the neighbors of v are in the V1. In this paper, we confirm this conjecture for some bipartite graphs, crown graphs and windmill graphs.

On the (Δ + 2)-Total-Colorability of Planar Graphs with 7-Cycles Containing at Most Two Chords

The Total Coloring Conjecture (TCC) proposes that every simple graph G is (Δ + 2)-totally-colorable, where Δ is the maximum degree of G. For planar graph, TCC is open only in case Δ = 6. In this paper, we prove that TCC holds for planar graph with Δ = 6 and every 7-cycle contains at most two chords.

On the Degree Resistance Distance of Unicyclic Graphs

Let Gbe a connected graph with vertex set V(G). Then the degree resistance distance of Gis defined as DR(G)=∑{ u,v }⊆V(G)(d(u)+d(v))R(u,v), where d(u)is the degree of the vertex u, and R(u,v)is the degree resistance distance between uand vin graph G. A unicyclic graph is a connected graph with a unique cycle. In this paper, we characterize the unique graph with the third-maximum degree resistance distance among all unicyclic graphs with nvertices.

Automated knowledge graphs for complex systems (AutoGraCS): Applications to management of bridge networks

With the ability to harness the power of big data,the digital twin(DT)technology has been increasingly applied to the modeling and management of structures and infrastructure systems,such as buildings,bridges,and power distribution systems.Supporting these applications,an important family of methods are based on graphs.For DT applications in modeling and managing smart cities,large-scale knowledge graphs(KGs)are necessary to represent the complex interdependencies and model the urban infrastructure as a system of systems.To this end,this paper develops a conceptual framework:Automated knowledge Graphs for Complex Systems(AutoGraCS).In contrast to existing KGs developed for DTs,AutoGraCS can support KGs to account for interdependencies and statistical correlations across complex systems.The established KGs from AutoGraCS can then be easily turned into Bayesian networks for probabilistic modeling,Bayesian analysis,and adaptive decision supports.Besides,AutoGraCS provides flexibility in support of users’need to implement the ontology and rules when constructing the KG.With the user-defined ontology and rules,AutoGraCS can automatically generate a KG to represent a complex system consisting of multiple systems.The bridge network in Miami-Dade County,FL is used as an illustrative example to generate a KG that integrates multiple layers of data from the bridge network,traffic monitoring facilities,and flood water watch stations.

Coloring of some integer distance graphs

An integer distance graph is a graph G(Z, D) with the integer set Z as vertexset, in which an edge joining two vertices u and v if and only if | u - v | ∈ D, where D is a setof natural numbers. Using a related theorem in combinatorics and some conclusions known to us in thecoloring of the distance graph, the chromatic number _X(G) is determined in this paper that is ofthe distance graph G(Z, D) for some finite distance sets D containing {2, 3} with D = 4 andcontaining {2, 3, 5} with | D | = 5 by the method in which the combination of a few periodiccolorings.

Ramsey numbers r(K_(1, 4), G) for all three-partite graphs G of order six

In this paper, we use a combinatorial analysis method. In the complete graph K N with edges colored arbitrarily by red or blue, we consider the proposition of the subgraph of the red graph or blue graph induced by the neighborhood of some vertex in V(K N). Inspired by the main results of Jayawardene and Rousseau (Ars Combinatoria, 2000, 163-173), we determine the Ramsey numbers of r(K 1, 4, G), where G is the three-partite graph of order six without isolate vertex.

Maximum Number of Edges of (rK_t)-Free Graphs

With positive integers r,t and n,where n≥rt and t≥2,the maximum number of edges of a simple graph of order n is estimated,which does not contain r disjoint copies of K_r for r=2 and 3.

The Path-Positive Property on the Products of Graphs

The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. It is proved that:① If the graphs G 1 and G 2 are the connected graphs, then the Cartesian product, the lexicographic product and the strong direct product in the products of graphs, are the path positive graphs. ② If the tensor product is a path positive graph if and only if the graph G 1 and G 2 are the connected graphs, and the graph G 1 or G 2 has an odd cycle and max{ λ 1μ 1,λ nμ m}≥2 in which λ 1 and λ n [ or μ 1 and μ m] are maximum and minimum characteristic values of graph G 1 [ or G 2 ], respectively.

Hamiltonicity,neighborhood union and square graphs of claw-free graphs

Let G be a graph, the square graph G 2 of G is a graph satisfying V(G 2)=V(G) and E(G 2)=E(G)∪｛uv: dist G(u, v)=2｝ . In this paper, we use the technique of vertex insertion on l -connected ( l=k or k+1, k≥2 ) claw-free graphs to provide a unified proof for G to be Hamiltonian, 1 -Hamiltonian or Hamiltonian-connected. The sufficient conditions are expressed by the inequality concerning ∑ k i=0N(Y i) and n(Y) in G for each independent set Y=｛y 0, y 1, …, y k｝ of the square graph of G , where b ( 0<b<k+1 ) is an integer, Y i=｛y i, y i-1, …, y i-(b-1)｝Y for i∈｛0, 1, …, k｝ , where subscriptions of y j s will be taken modulo k+1 , and n(Y)=｛v∈ V(G): dist (v, Y)≤ 2｝ .

Neighborhood Union of Essential Sets and Hamiltonicity of Claw-Free Graphs

Let G be a graph, an independent set Y in G is called an essential independent set (or essential set for simplicity), if there is {y 1,y 2} Y such that dist (y 1,y 2)=2. In this paper, we will use the technique of the vertex insertion on l connected ( l=k or k+1,k≥2 ) claw free graphs to provide a unified proof for G to be hamiltonian or 1 hamiltonian, the sufficient conditions are expressed by the inequality concerning ∑ki=0N(Y i) and n(Y) for each essential set Y={y 0,y 1,...,y k} of G , where Y i={y i,y i-1 ,...,y i-(b-1) }Y for i∈{0,1,...,k} (the subscriptions of y j ’s will be taken modulo k+1 ), b ( 0【b【k+1 ) is an integer, and n(Y)={v∈V(G): dist (v,Y)≤2 }.

Circular L(j,k)-labeling numbers of trees and products of graphs

Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are at distance two,where a-bm=min{a-b,m-a-b}. The minimum m such that there exists a circular m-L（j, k）-labeling of G is called the circular L（j, k）-labeling number of G and is denoted by σj, k（G）. For any two positive integers j and k with j≤k,the circular L（j, k）-labeling numbers of trees, the Cartesian product and the direct product of two complete graphs are determined.

基于GraphSAGE网络的藏文短文本分类研究

文本分类是自然语言处理领域的重要研究方向,由于藏文数据的稀缺性、语言学特征抽取的复杂性、篇章结构的多样性等因素导致藏文文本分类任务进展缓慢。因此,该文以图神经作为基础模型进行改进。首先,在“音节-音节”“音节-文档”建模的基础上,融合文档特征,采用二元分类模型动态网络构建“文档-文档”边,以充分挖掘短文本的全局特征,增加滑动窗口,减少模型的计算复杂度并寻找最优窗口取值。其次,针对藏文短文本的音节稀疏性,首次引入GraphSAGE作为基础模型,并探究不同聚合方式在藏文短文本分类上的性能差异。最后,为捕获节点间关系的异质性,对邻居节点进行特征加权再平均池化以增强模型的特征提取能力。在TNCC标题文本数据集上,该文模型的分类准确率达到了62.50%,与传统GCN、原始GraphSAGE和预训练语言模型CINO相比,该方法在分类准确率上分别提高了2.56%、1%和2.4%。

PROPERTIES OF SPECTRA OF GRAPHS AND LINE GRAPHS

Let G be a simple connected graph with n vertices and m edges,L G be the line graph of G and λ 1(L G)≥λ 2(L G)≥...≥λ m(L G) be the eigenvalues of the graph L G.In this paper,the range of eigenvalues of a line graph is considered.Some sharp upper bounds and sharp lower bounds of the eigenvalues of L G are obtained.In particular,it is proved that-2cos(πn)≤λ n-1 (L G)≤n-4 and λ n(L G)=-2 if and only if G is bipartite.