A POLYNOMIAL ALGORITHM FOR FINDING THEMINIMUM FEEDBACK VERTEX SET OF A3-REGULAR SIMPLE GRAPH

A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided.

The Cordiality on the Union of 3-regular Connected Graph and Cycle

Diab proved the following graphs are Cordial;Pm K1,n if and only if(m,n) =(1,2);Cm K1,n;Pm Kn;Cm Kn for all m and n except m ≡ 2(mod 4).In this paper,we proved the Cordiality on the union of 3-regular connected graph K3 and cycle Cm.First we have the Lemma 2,if uv ∈ E(G),G is Cordial,we add 4 vertices x,y,z,w in sequence to the edge uv,obtain a new graph denoted by G*,then G* is still Cordial,by this lemma,we consider four cases on the union of 3-regular connected graph R3,and for every case we distinguish four subcases on the cycle Cm.

A Note on the Girth of 3-Regular Hamiltonian Graph

It is well-known that the Petersen graph is nonhamiltonian.A very short proof for this result was presented in[2]due to D.B.West.In this note,by extending the proof technique in[2],we briefly show that the girth of every 3-regular hamiltonian graph on n≥10 vertices is at most(n+4)/3.

SGT-Net: A Transformer-Based Stratified Graph Convolutional Network for 3D Point Cloud Semantic Segmentation

In recent years,semantic segmentation on 3D point cloud data has attracted much attention.Unlike 2D images where pixels distribute regularly in the image domain,3D point clouds in non-Euclidean space are irregular and inherently sparse.Therefore,it is very difficult to extract long-range contexts and effectively aggregate local features for semantic segmentation in 3D point cloud space.Most current methods either focus on local feature aggregation or long-range context dependency,but fail to directly establish a global-local feature extractor to complete the point cloud semantic segmentation tasks.In this paper,we propose a Transformer-based stratified graph convolutional network(SGT-Net),which enlarges the effective receptive field and builds direct long-range dependency.Specifically,we first propose a novel dense-sparse sampling strategy that provides dense local vertices and sparse long-distance vertices for subsequent graph convolutional network(GCN).Secondly,we propose a multi-key self-attention mechanism based on the Transformer to further weight augmentation for crucial neighboring relationships and enlarge the effective receptive field.In addition,to further improve the efficiency of the network,we propose a similarity measurement module to determine whether the neighborhood near the center point is effective.We demonstrate the validity and superiority of our method on the S3DIS and ShapeNet datasets.Through ablation experiments and segmentation visualization,we verify that the SGT model can improve the performance of the point cloud semantic segmentation.

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.

Cover a 3-regular Claw-free Graph by Induced Matchings

The induced matching cover number of a graph G without isolated vertices, denoted by imc(G),is the minimum integer k such that G has k induced matchings {M1,M2,···,Mk}such that,V(M1)∪V(M2)∪···∪V(Mk)covers V(G).This paper shows that,if G is a 3-regular claw-free graph,then imc(G)∈{2,3}.

GRAPH GRAMMAR METHOD FOR 3-D CORNER DETECTION

Most of local feature descriptors assume that the scene is planar. In the real scene, the captured images come from the 3-D world. 3-D corner as a novel invariant feature is important for the image matching and the object detection, while automatically discriminating 3-D corners from ordinary corners is difficult. A novel method for 3-D corner detection is proposed based on the image graph grammar, and it can detect the 3-D features of corners to some extent. Experimental results show that the method is valid and the 3-D corner is useful for image matching.

Global Dynamic Modeling of Electro-Hydraulic 3-UPS/S Parallel Stabilized Platform by Bond Graph

Dynamic modeling of a parallel manipulator（PM） is an important issue. A complete PM system is actually composed of multiple physical domains. As PMs are widely used in various fields, the importance of modeling the global dynamic model of the PM system becomes increasingly prominent. Currently there lacks further research in global dynamic modeling. A unified modeling approach for the multi-energy domains PM system is proposed based on bond graph and a global dynamic model of the 3-UPS/S parallel stabilized platform involving mechanical and electrical-hydraulic elements is built. Firstly, the screw bond graph theory is improved based on the screw theory, the modular joint model is modeled and the normalized dynamic model of the mechanism is established. Secondly, combined with the electro-hydraulic servo system model built by traditional bond graph, the global dynamic model of the system is obtained, and then the motion, force and power of any element can be obtained directly. Lastly, the experiments and simulations of the driving forces, pressure and flow are performed, and the results show that, the theoretical calculation results of the driving forces are in accord with the experimental ones, and the pressure and flow of the first limb and the third limb are symmetry with each other. The results are reasonable and verify the correctness and effectiveness of the model and the method. The proposed dynamic modeling method provides a reference for modeling of other multi-energy domains system which contains complex PM.

SCORE SETS IN ORIENTED 3-PARTITE GRAPHS

Abstract. Let D （U, V, W） be an oriented 3-partite graph with ｜ U ｜ = p, ｜V｜ = q and ｜W ｜ = r. For any vertex x in D（U,V,W）, let dx^＋ and dui^- be the outdegree and indegree ofx respectively. Define aui （or simply ai） = q ＋ r ＋ dui^＋ - dui^-, bvj （or simply b j） = p ＋ r ＋ d^＋vj - d^-vj and cwk （or simply ck） =p ＋ q ＋ dwk^＋ -dwk^- as the scores of ui in U,vj in V and wk in W respectively. The set A of distinct scores of the vertices of D（U, V, W） is called its score set. In this paper, we prove that if a1 is a non-negative integer, ai（2 ≤ i ≤ n - 1） are even positive integers and an is any positive integer, then for n 〉 3, there exists an oriented 3-partite graph with the score set A ={a1,Σ2i=1 ai,…,Σni=1 ai}, except when A = {0, 2, 3}. Some more results for score sets in oriented 3-partite graphs are obtained.

The L(3,2,1)-labeling on Bipartite Graphs

An L（3, 2, 1）-labeling of a graph G is a function from the vertex set V（G） to the set of all nonnegative integers such that ｜f（u）-f（v）｜≥3 if dG（u,v） = 1, ｜f（u）-f（v）｜≥2 if dG（u,v） = 2, and ｜f（u）-f（v）｜≥1 if dG（u,v） = 3. The L（3, 2,1）-labeling problem is to find the smallest number λ3（G） such that there exists an L（3, 2,1）-labeling function with no label greater than it. This paper studies the problem for bipartite graphs. We obtain some bounds of λ3 for bipartite graphs and its subclasses. Moreover, we provide a best possible condition for a tree T such that λ3（T） attains the minimum value.

GCR-Net:3D Graph convolution-based residual network for robust reconstruction in cerenkov luminescence tomography

Cerenkov Luminescence Tomography(CLT)is a novel and potential imaging modality which can display the three-dimensional distribution of radioactive probes.However,due to severe ill-posed inverse problem,obtaining accurate reconstruction results is still a challenge for traditional model-based methods.The recently emerged deep learning-based methods can directly learn the mapping relation between the surface photon intensity and the distribution of the radioactive source,which effectively improves the performance of CLT reconstruction.However,the previously proposed deep learning-based methods cannot work well when the order of input is disarranged.In this paper,a novel 3D graph convolution-based residual network,GCR-Net,is proposed,which can obtain a robust and accurate reconstruction result from the photon intensity of the surface.Additionally,it is proved that the network is insensitive to the order of input.The performance of this method was evaluated with numerical simulations and in vivo experiments.The results demonstrated that compared with the existing methods,the proposed method can achieve efficient and accurate reconstruction in localization and shape recovery by utilizing threedimensional information.

3D scene graph prediction from point clouds

Background In this study,we propose a novel 3D scene graph prediction approach for scene understanding from point clouds.Methods It can automatically organize the entities of a scene in a graph,where objects are nodes and their relationships are modeled as edges.More specifically,we employ the DGCNN to capture the features of objects and their relationships in the scene.A Graph Attention Network(GAT)is introduced to exploit latent features obtained from the initial estimation to further refine the object arrangement in the graph structure.A one loss function modified from cross entropy with a variable weight is proposed to solve the multi-category problem in the prediction of object and predicate.Results Experiments reveal that the proposed approach performs favorably against the state-of-the-art methods in terms of predicate classification and relationship prediction and achieves comparable performance on object classification prediction.Conclusions The 3D scene graph prediction approach can form an abstract description of the scene space from point clouds.

不超过7阶的3-关系图的刻画

给定一个图G,如果存在一个边标号树T,使得树T的叶子集等于图G的顶点集,并且树T任何叶子x到叶子y的唯一路径上的边标号之和为3当且仅当xy为图G的边,那么称图G是一个3-关系图.该文讨论了什么样的图是3-关系图,证明了图G是3-关系图的必要条件为图G是二部图,即只要图G包含奇圈,则图G不是3-关系图.更进一步,完全刻画了圈为3-关系图的充要条件,即一个圈是3-关系图当且仅当圈为偶圈,并且给出了偶圈相对应的边标号树.最后讨论了比较小的图为3-关系图的条件,即证明了阶至多为7的图是3-关系图的充分必要条件为图G是二部图.

基于边权的最小权重3路顶点覆盖算法

城际仓储选址通常可以转化为顶点覆盖问题,顶点覆盖问题是一种经典的NP难问题。针对最小权重3路顶点覆盖问题,设计了基于边权和顶点度的贪心策略,构建了1个两阶段的最小权重3路顶点覆盖算法。通过与2种较优的最小权重3路顶点覆盖算法进行对比实验分析可知,本文提出的算法在城际物流仓储选址问题中具有较好的效果,最小权重和分别减少了3.34和1.13个百分点。

若干类3-正则图的Smarandachely邻点全染色的界

针对3-正则图的结构性质,利用组合分析法和构造染色的方法讨论了若干类3-正则图的Smarandachely邻点全染色,并得到了其Smarandachely邻点全色数,进一步验证了图的Smarandachely邻点全染色猜想.

关于3-正则图的平均亏格(英文)

一个图 Ｇ的 ２－因子 Ｆ是一个使得每个点ｖ在 Ｆ中的度 ｄＦ（ｖ）＝２的 Ｇ的生成子图．易知 Ｆ中的每个圈是点不交的．如果 Ｆ中每个圈的长度为 ４，我们说 Ｇ有四边形 ２－因子Ｆ．我们首先在３－正则图上定义了３种扩张运算，然后讨论这些运算对平均亏格的影响．运用扩张运算，我们研究了含有四边形２－因子的３－正则图的平均亏格，得到了３－正则图的平均亏格与最大亏格之间的关系．

关于不含3正则子图图的最大边数

对无自环、无重边的简单图，Ｅｒｄｏｓ和Ｓａｕｃｅｒ在１９７４年提出如下问题：设 ｆ（ｐ） 是ｐ个顶点的不含３正则子图图的最大可能边数，确定ｆ（ｐ）．本文对ｐ ≥４、４≤ｐ≤４０给出了ｆ（ｐ）的下界，对４ｐ刁≤１６给出了ｆ（ｐ）的值，并对４≤ｐ ≤１５得出了所有的极图．

3类3-正则图中的完美对集数

Lovász L和Plummer M提出了一个猜想:任意2-边连通图至少有指数多个完美对集.这个猜想至今没有被证明,也没有被否定.本文用划分、求和,再嵌套递推的方法给出了3类特殊图完美对集数目的显式表达式,从而验证了Lovász L和Plummer M猜想在这3类图上的正确性.

3-连通3-正则图生成树外的可去边(英文)

G是3-连通图,e是G中的一条边。若G-e是3-连通图的一个剖分,则称e是3-连通图的可去边。否则,e是G中不可去边。本文给出3-连通3-正则图中生成树外可去边的分布情况及数目。

图P_n^3的优美标号

定义了图 P3 n,证明了当 n =6 k +2及 n =6 k +4时 ,图 P3 n是优美图 ,并得到它们的优美标号 ,其中 k是任意自然数 .