探索金鱼图的奇优美性

给出了奇优美图和二分奇优美图的概念,并定义了金鱼图,证明了在鱼头为不同图形的情况下,金鱼图仍然是奇优美的,且是二分奇优美的.还证明了:对一个奇优美图H和一棵二分奇优美树T,用一条边连接T的一个顶点和H的标号基点u_0后所得到的金鱼图仍是奇优美图.     

→Pn和→Cn的有向优美性

优美图可用在图论中的某些H-分解问题中,很多人研究无向图的优美标号.研究有向优美标号,通过对阶数奇偶性的讨论,给出了n(≥2)阶有向路(→Pn)和n(≥3)阶有向圈(→Cn)是有向优美的充分条件.     

(向量)R_n和(向量)G_n的有向优美性

优美图可用在图论中的某些H-分解问题中,很多人研究无向图的优美标号.研究有向优美标号,通过对阶数奇偶性的讨论,给出了n(≥2)阶有向路(向量)P_n和n(≥3)阶有向(向量)C_n圈是有向优美的充分条件.     

有向图(→C)n×(→P)2的优美性

研究了有向图(→C)n×(→P)2的优美性,利用搜索图的标号的算法与数学证明相结合的方法,证实了有向图(→C)n×(→P)2为优美图,其中n为任意正整数.     

图P^3n的奇优美标号算法

本文讨论了图P^3n的奇优美性,给出了图只奇优美标号算法．     

有向图C(向量)_n×P(向量)_2的优美性

研究了有向C(向量)_n×P(向量)_2的优美性,利用搜索图的标号的算法与数学证明相结合的方法,证实了有向图C(向量)_n×P(向量)_2为优美图,其中n为任意正整数.     

有向图n·_3优美的进一步性质

本文在我们以往研究基础上 ,得到了有向图 n· C 3优美的进一步性质 :两个无交有向图 n· C 3各自的公共顶点与一个新增加的顶点 ,分别用有向弧来连接 ,使该新增加顶点的出度为 2或入度为 2时 ,这样连接而得的有向图为优美图     

奇优美图的构造

图G的标号是指G的顶点集到一个整数集的映射f,且对e=uv∈E(G)由f(u)和f(v)诱导出边e的标号f(uv).本文给出了二分奇优美图的概念,证明了一个图是二分奇优美的当且仅当它是二分优美的,并给出了一些构造奇优美图的方法.     

有向图4_n的优美性

研究了有向图mn的优美性,利用搜索图的标号的算法与数学证明相结合的方法,证明了有向图4n为优美图,其中n为任意正整数.     

有向图4-→Cn的优美性

研究了有向图m→C n 的优美性,利用搜索图的标号的算法与数学证明相结合的方法,证明了有向图4→ Cn 为优美图,其中n为任意正整数。     

A compact labeling scheme for series-parallel graphs

A linear time labeling algorithm is presented for series-parallel graphs. The labels enable us to efficiently implement dynamic programming algorithms for sequencing problems with series-parallel precedence constraints. The labeling scheme can also be used to efficiently count and generate the initial sets, terminal sets and independent sets in transitive series-parallel digraphs and to provide a characterization of the maximal independent sets in transitive digraphs.     

Vertex magic total labelings of 2-regular graphs

A vertex magic total (VMT) labeling of a graph $G=(V,E)$ is a bijection from the set of vertices and edges to the set of integers defined by $\lambda :V\cup E\to \{1,2,\dots ,|V|+|E\left|\right\}$ so that for every $x\in V$, $w\left(x\right)=\lambda \left(x\right)+{\sum }_{xy\in E}\lambda \left(xy\right)=k$, for some integer $k$. A VMT labeling is said to be a super VMT labeling if the vertices are labeled with the smallest possible integers, $1,2,\dots ,\left|V\right|$. In this paper we introduce a new method to expand some known VMT labelings of 2-regular graphs.     

A classification of all arc-locally semicomplete digraphs

Arc-locally semicomplete digraphs were introduced by Bang-Jensen as a common generalization of both semicomplete and semicomplete bipartite digraphs in 1993. Later, Bang-Jensen (2004), Galeana-Sánchez and Goldfeder (2009) and Wang and Wang (2009) provided a characterization of strong arc-locally semicomplete digraphs. In this paper, we provide a characterization of strong and non-strong arc-locally semicomplete digraphs which generalizes some results by Bang-Jensen.     

On the weak distance-regularity of Moore-type digraphs

We prove that Moore digraphs, and some other classes of extremal digraphs, are weakly distance-regular in the sense that there is an invariance of the number of walks between vertices at a given distance. As weakly distance-regular digraphs, we then compute their complete spectrum from a ‘small’ intersection matrix. This is a very useful tool for deriving some results about their existence and/or their structural properties. For instance, we present here an alternative and unified proof of the existence results on Moore digraphs, Moore bipartite digraphs and, more generally, Moore generalized p-cycles. In addition, we show that the line digraph structure appears as a characteristic property of any Moore generalized p-cycle of diameter D?≥?2p.     

Cayley digraphs and graphs

We shortly recall some definitions that involve refinements of connectivity, and a theorem of Y.O. Hamidoune. We consider some aspects of Cayley digraphs and vertex- and arc-transitive digraphs that he investigated.     

Constructing highly arc transitive digraphs using a direct fibre product

We introduce a construction of highly arc transitive digraphs using a direct fibre product. This product generalizes some known classes of highly arc transitive digraphs but also allows us to construct new ones. We use the product to obtain counterexamples to a conjecture advanced by Cameron, Praeger and Wormald on the structure of certain highly arc transitive digraphs.     

The kth upper and lower bases of primitive nonpowerful minimally strong signed digraphs

In this article, we study the kth upper and lower bases of primitive nonpowerful minimally strong signed digraphs. A bound on the kth upper bases for primitive nonpowerful minimally strong signed digraphs is obtained, and the equality case of the bound is characterized. For the kth lower bases, we obtain some bounds. For some cases, the bounds are best possible and the extremal signed digraphs are characterized. We also show that there exist ‘gaps’ in both the kth upper base set and the kth lower base set of primitive nonpowerful minimally strong signed digraphs.     

Ihara zeta functions of digraphs

After defining and exploring some of the properties of Ihara zeta functions of digraphs, we improve upon Kotani and Sunada’s bounds on the poles of Ihara zeta functions of undirected graphs by considering digraphs whose adjacency matrices are directed edge matrices.     

有向图字典乘积的代数群性质

字典乘积有向图G_1→⊙G_2是通过已知阶数较小的有向图G_1和G_2构造来的,这些小有向图G_1和G_2的拓扑结构和性质肯定影响大有向图G_1→⊙G_2的拓扑结构和性质.运用群论方法,证明了有向图字典乘积的一些代数性质,如:结合律、分配律等.