The <Emphasis Type="Italic">k</Emphasis>-point exponent set of primitive digraphs with girth 2

Let D = （V, E） be a primitive digraph. The vertex exponent of D at a vertex v∈ V, denoted by expD（v）, is the least integer p such that there is a v →u walk of length p for each u ∈ V. Following Brualdi and Liu, we order the vertices of D so that exPD（V1） ≤ exPD（V2） …≤ exPD（Vn）. Then exPD（Vk） is called the k- point exponent of D and is denoted by exPD （k）, 1≤ k ≤ n. In this paper we define e（n, k） ：= max{expD （k） ｜ D ∈ PD（n, 2）} and E（n, k） ：= {exPD（k）｜ D ∈ PD（n, 2）}, where PD（n, 2） is the set of all primitive digraphs of order n with girth 2. We completely determine e（n, k） and E（n, k） for all n, k with n ≥ 3 and 1 ≤ k ≤ n.     

On hereditary clique-Helly self-clique graphs

A graph is clique-Helly if any family of mutually intersecting (maximal) cliques has non-empty intersection, and it is hereditary clique-Helly (HCH) if its induced subgraphs are clique-Helly. The clique graph of a graph G is the intersection graph of its cliques, and G is self-clique if it is connected and isomorphic to its clique graph. We show that every HCH graph is an induced subgraph of a self-clique HCH graph, and give a characterization of self-clique HCH graphs in terms of their constructibility starting from certain digraphs with some forbidden subdigraphs. We also specialize this results to involutive HCH graphs, i.e. self-clique HCH graphs whose vertex-clique bipartite graph admits a part-switching involution.     

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

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

Minimum Eulerian circuits and minimum de Bruijn sequences

Given a digraph (directed graph) with a labeling on its arcs, we study the problem of finding the Eulerian circuit of lexicographically minimum label. We prove that this problem is NP-complete in general, but if the labelling is locally injective (arcs going out from each vertex have different labels), we prove that it is solvable in linear time by giving an algorithm that constructs this circuit. When this algorithm is applied to a de Bruijn graph, it obtains the de Bruijn sequences with lexicographically minimum label.     

Connected -tuple twin domination in de Bruijn and Kautz digraphs

For a digraph G, a k-tuple twin dominating set D of G for some fixed k≥1 is a set of vertices such that every vertex is adjacent to at least k vertices in D, and also every vertex is adjacent from at least k vertices in D. If the subgraph of G induced by D is strongly connected, then D is called a connected k-tuple twin dominating set of G. In this paper, we give constructions of minimal connected k-tuple twin dominating sets for de Bruijn digraphs and Kautz digraphs.     

On Hamiltonicity of circulant digraphs of outdegree three

This paper deals with Hamiltonicity of connected loopless circulant digraphs of outdegree three with connection set of the form {a,ka,c}, where k is an integer. In particular, we prove that if k=−1 or k=2 such a circulant digraph is Hamiltonian if and only if it is not isomorphic to the circulant digraph on 12 vertices with connection set {3,6,4}.     

Every cycle-connected multipartite tournament has a universal arc

A digraph D is cycle-connected if for every pair of vertices u,v∈V(D) there exists a directed cycle in D containing both u and v. In 1999, Ádám [A. Ádám, On some cyclic connectivity properties of directed graphs, Acta Cybernet. 14 (1) (1999) 1-12] posed the following problem. Let D be a cycle-connected digraph. Does there exist a universal arc in D, i.e., an arc e∈A(D) such that for every vertex w∈V(D) there is a directed cycle in D containing both e and w?A c-partite or multipartite tournament is an orientation of a complete c-partite graph. Recently, Hubenko [A. Hubenko, On a cyclic connectivity property of directed graphs, Discrete Math. 308 (2008) 1018-1024] proved that each cycle-connected bipartite tournament has a universal arc. As an extension of this result, we show in this note that each cycle-connected multipartite tournament has a universal arc.     

典型串并联系统的备件库存优化模型

选取典型串并联系统的备件库存优化为研究对象,以系统供应可用度最大为目标,备件总购置费为约束条件构建备件库存优化模型,给出基于边际分析法的优化算法.经示例分析,验证了该模型的可行性和有效性,结果可为备件保障经费的合理配置提供理论依据.     

一类特殊的本原不可幂对称带号有向图的基指数的上界

一个本原不可幂带号有向图s的基指数l(s)是这样的最小正整数l,使得在s中,从任意一点u到任意一点v都有一对长为l的sssD途径.本文研究了n阶最小奇圈长为r的本原不可幂对称带号有向图的基指数,给出了这类有向图的基指数的最大值.     

本原对称无环带号有向图的基指数与基指数集

In this paper,we study the bases and base sets of primitive symmetric loop-free (generalized)signed digraphs on n vertices.We obtain sharp upper bounds of the bases,and show that the base sets of the classes of such digraphs are{2,3,...,2n-1}.We also give a new proof of an important result obtained by Cheng and Liu.