Nowhere-zero 4-flow in almost Petersen-minor free graphs

Tutte [W.T. Tutte, On the algebraic theory of graph colorings, J. Combin. Theory 1 (1966) 15-20] conjectured that every bridgeless Petersen-minor free graph admits a nowhere-zero 4-flow. Let be the graph obtained from the Petersen graph by contracting μ edges from a perfect matching. In this paper we prove that every bridgeless -minor free graph admits a nowhere-zero 4-flow.     

An application of Vizing and Vizing-like adjacency lemmas to Vizing’s Independence Number Conjecture of edge chromatic critical graphs

In 1968, Vizing conjectured that, if G is a Δ-critical graph with n vertices, then , where α(G) is the independence number of G. In this note, we apply Vizing and Vizing-like adjacency lemmas to this problem and obtain better bounds for Δ∈{7,…,19}.     

Zero-divisor semigroups and refinements of a star graph

Let G be a refinement of a star graph with center c. Let be the subgraph of G induced on the vertex set V(G)?{c or end vertices adjacent to c}. In this paper, we completely determine the structure of commutative zero-divisor semigroups S whose zero-divisor graph G=Γ(S) and S satisfy one of the following properties: (1) has at least two connected components, (2) is a cycle graph C_n of length n≥5, (3) is a path graph P_n with n≥6, (4) S is nilpotent and Γ(S) is a finite or an infinite star graph. For any finite or infinite cardinal number n≥2, we prove that for any nilpotent semigroup S with zero element 0, S⁴=0 if Γ(S) is a star graph K_1,n. We prove that there is exactly one nilpotent semigroup S such that S³≠0 and Γ(S)≅K_1,n. For several classes of finite graphs G which are refinements of a star graph, we also obtain formulas to count the number of non-isomorphic corresponding semigroups.     

Vertex reconstruction in Cayley graphs

In this survey paper we review recent results on the vertex reconstruction problem (which is not related to Ulam’s problem) in Cayley graphs. The problem of reconstructing an arbitrary vertex x from its r-neighbors, that are, vertices at distance at most r from x, consists of finding the minimum restrictions on the number of r-neighbors when such a reconstruction is possible. We discuss general results for simple, regular and Cayley graphs. To solve this problem for given Cayley graphs, it is essential to investigate their structural and combinatorial properties. We present such properties for Cayley graphs on the symmetric group and the hyperoctahedral group (the group of signed permutations) and overview the main results for them. The choice of generating sets for these graphs is motivated by applications in coding theory, computer science, molecular biology and physics.     

Pan-connectedness of graphs with large neighborhood unions

Let G be a simple graph with n vertices. For any , let , and , and and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC ₂(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC ₂(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC ₂(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.      

完全多部图的树划分数的直观证明

r-边染色图G的树划分数tr(G)定义为最小的正整数k,使得只要用r种颜色对图G进行边染色,则存在至多k个顶点不交的单色树覆盖图G的所有顶点.K aneko等确定了t2(K(n1,n2,…,nk))的精确表达式.本文给出了该表达式的一个直观证明.     

基于多信号流图模型的导弹系统级故障诊断技术研究

为了实现对导弹装备系统级故障的诊断,提出了基于多信号流图模型的导弹故障诊断方法;该方法利用多信号流图模型建立系统的层次结构模型,在对导弹系统级测试性指标进行分析的同时,生成故障模式-测试相关性矩阵;在导弹测试出现故障时,利用故障模式与测试的相关性对相关性矩阵进行化简后,可将故障定位到具体LRU;最后,利用某型导弹电气系统对该方法进行了验证,试验结果证明,该方法对于导弹系统级的测试性建模与分析是有效的,利用该模型能够对导弹系统级故障进行准确定位。     

Curvature notions on graphs

We survey some geometric and analytic results under the assumptions of combinatorial curvature bounds for planar/semiplanar graphs and curvature dimension conditions for general graphs.     

Universality for the Distance in Finite Variance Random Graphs

We generalize the asymptotic behavior of the graph distance between two uniformly chosen nodes in the configuration model to a wide class of random graphs. Among others, this class contains the Poissonian random graph, the expected degree random graph and the generalized random graph (including the classical Erdős-Rényi graph). In the paper we assign to each node a deterministic capacity and the probability that there exists an edge between a pair of nodes is equal to a function of the product of the capacities of the pair divided by the total capacity of all the nodes. We consider capacities which are such that the degrees of a node have uniformly bounded moments of order strictly larger than two, so that, in particular, the degrees have finite variance. We prove that the graph distance grows like log  _ν N, where the ν depends on the capacities and N denotes the size of the graph. In addition, the random fluctuations around this asymptotic mean log  _ν N are shown to be tight. We also consider the case where the capacities are independent copies of a positive random Λ with , for some constant c and τ>3, again resulting in graphs where the degrees have finite variance. The method of proof of these results is to couple each member of the class to the Poissonian random graph, for which we then give the complete proof by adapting the arguments of van der Hofstad et al. (Random Struct. Algorithms 27(2):76–123, 2005).