Bubble-sort图和Modified Bubble-sort图的自同构群

Bubble-Sort图和Modified Bubble-Sort图是两类特殊的Cayley图,由于其在网络构建中的应用而受到广泛关注.本文完全确定了这两类图的自同构群.     

Disjoint chorded cycles in graphs

We propose the following conjecture to generalize results of Pósa and of Corrádi and Hajnal. Let r,s be nonnegative integers and let G be a graph with |V(G)|≥3r+4s and minimal degree δ(G)≥2r+3s. Then G contains a collection of r+s vertex disjoint cycles, s of them with a chord. We prove the conjecture for r=0,s=2 and for s=1. The corresponding extremal problem, to find the minimum number of edges in a graph on n vertices ensuring the existence of two vertex disjoint chorded cycles, is also settled.     

Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs

We investigate the complexity of several domination problems on the complements of bounded tolerance graphs and the complements of trapezoid graphs. We describe an O(n² log⁵ n) time and O(n²) space algorithm to solve the domination problem on the complement of a bounded tolerance graph, given a square embedding of that graph. We also prove that domination, connected domination and total domination are all NP-complete on co-trapezoid graphs.     

A sufficient condition for boundedness of tolerance graphs

Golumbic, Monma, and Trotter showed that every tolerance graph for which no vertex neighborhood is contained in another vertex neighborhood is a bounded tolerance graph. We strengthen this result by weakening the neighborhood condition. In this way, more tolerance graphs can be recognized as bounded. Our argument relies on a variation of the concept of “assertive vertices”.     

Self-spanner graphs

We introduce the (k,ℓ)-self-spanners graphs to model non-reliable interconnection networks. Such networks can be informally characterized as follows: if at most ℓ edges have failed, as long as two vertices remain connected, the distance between these vertices in the faulty graph is at most k times the distance in the non-faulty graph. By fixing the values k and ℓ (called stretch factor and fault-tolerance, respectively), we obtain specific new graph classes. We first provide characterizational, structural, and computational results for these classes. Then, we study relationships between the introduced classes and special graphs classes (distance-hereditary graphs, cographs, and chordal graphs), and common network topologies (grids, tori, hypercubes, butterflies, and cube-connected cycles) as well.     

Cover-incomparability graphs and chordal graphs

The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs.     

Tolerance graphs,and orders

We show that, if a tolerance graph is the complement of a comparability graph, it is a trapezoid graph, i.e., the complement of an order of interval dimension at most 2. As consequences we are able to give obstructions for the class of bounded tolerance graphs and to give an example of a graph that is alternatingly orientable but not a tolerance graph. We also characterize the tolerance graphs among complements of trees. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 129–140, 1998     

Cycles in 2-connected graphs

Let be a class of graphs on n vertices. For an integer c, let be the smallest integer such that if G is a graph in with more than edges, then G contains a cycle of length more than c. A classical result of Erdös and Gallai is that if is the class of all simple graphs on n vertices, then . The result is best possible when n-1 is divisible by c-1, in view of the graph consisting of copies of K_c all having exactly one vertex in common. Woodall improved the result by giving best possible bounds for the remaining cases when n-1 is not divisible by c-1, and conjectured that if is the class of all 2-connected simple graphs on n vertices, thenwhere , 2tc/2, is the number of edges in the graph obtained from K_c+1-t by adding n-(c+1-t) isolated vertices each joined to the same t vertices of K_c+1-t. By using a result of Woodall together with an edge-switching technique, we confirm Woodall's conjecture in this paper.     

Colourings of graphs with two consecutive odd cycle lengths

In 1992 Gyárfás showed that a graph G having only k odd cycle lengths is (2k+1)-colourable, if it does not contain a K_2k+2. In this paper, we will present the results for graphs containing only odd cycles of length 2m−1 and 2m+1 as done in [S. Matos Camacho, Colourings of graph with prescribed cycle lengths, diploma thesis, TU Bergakademie Freiberg, 2006. [3]]. We will show that these graphs are 4-colourable.     

探针区间图和STS-探针区间图的刻划

该文首先引入了探针区间序来刻划探针区间图;接着给出STS-探针区间图的探针区间完备的一种构造方法,并借此得到二部图G是相对于给定顶点划分的STS-探针区间图的一个充要条件;同时也说明了STS-探针区间图其实就是其他文献中被独立研究的凸二部图.最后基于前面给出的STS-探针区间图的刻划结果提供了两种简单的O(V E)时间的STS-探针区间图的判别算法.     

Balanced Cayley graphs and balanced planar graphs

A balanced graph is a bipartite graph with no induced circuit of length . These graphs arise in integer linear programming. We focus on graph-algebraic properties of balanced graphs to prove a complete classification of balanced Cayley graphs on abelian groups. Moreover, in this paper, we prove that there is no cubic balanced planar graph. Finally, some remarkable conjectures for balanced regular graphs are also presented. The graphs in this paper are simple.     

Equistable graphs, general partition graphs, triangle graphs, and graph products

In this paper we examine the connections between equistable graphs, general partition graphs and triangle graphs. While every general partition graph is equistable and every equistable graph is a triangle graph, not every triangle graph is equistable, and a conjecture due to Jim Orlin states that every equistable graph is a general partition graph. The conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs.Exploiting the combinatorial features of triangle graphs and general partition graphs, we verify Orlin’s conjecture for several graph classes, including AT-free graphs and various product graphs. More specifically, we obtain a complete characterization of the equistable graphs that are non-prime with respect to the Cartesian or the tensor product, and provide some necessary and sufficient conditions for the equistability of strong, lexicographic and deleted lexicographic products. We also show that the general partition graphs are not closed under the strong product, answering a question by McAvaney et al.     

Characterization of digraphs with equal domination graphs and underlying graphs

A domination graph of a digraph D, dom(D), is created using the vertex set of D and edge {u,v}∈E[dom(D)] whenever (u,z)∈A(D) or (v,z)∈A(D) for every other vertex z∈V(D). The underlying graph of a digraph D, UG(D), is the graph for which D is a biorientation. We completely characterize digraphs whose underlying graphs are identical to their domination graphs, UG(D)=dom(D). The maximum and minimum number of single arcs in these digraphs, and their characteristics, is given.     

修正冒泡排序网络的边偶泛圈性

对于一个二部图G,如果在G中存在任意长为偶数l(4≤l≤|V(G)|)的圈,则称这个二部图G是偶泛圈的:如果对G中任意一边e,在G中存在任意长为偶数l(4≤l≤|V(G)|)且包含e的圈,则称这个二部图G是边偶泛圈的.修正冒泡排序网络是互连网络中的一个重要的Cayley图模型.在此,证明了对任意的自然数n,当n≥3时,修正冒泡排序网络Y_n是偶泛圈的,同时也是边偶泛圈的.     

Fault tolerance of vertex pancyclicity in alternating group graphs

We study fault tolerance of vertex k pancyclicity of the alternating group graph AG_n. A graph G is vertex k pancyclic, if for every vertex p∈G, there is a cycle going through p of every length from k to |G|. Xue and Liu [Z.-J. Xue, S.-Y. Liu, An optimal result on fault-tolerant cycle-embedding in alternating group graphs, Inform. Proc. Lett. 109 (2009) 1197-1201] put the conjecture that AG_n is (2n-7)-fault-tolerant vertex pancyclic, which means that if the number of faults |F|?2n-7, then AG_n-F is still vertex pancyclic. Chang and Yang [J.-M. Chang, J.-S. Yang, Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput. 197 (2008) 760-767] showed that for the shortest cycles the fault-tolerance of AG_n is much lower. They noted that with n-2 faults one can cut all 3-cycles going through a given vertex p (it is easy to observe that the same set of faults cuts all 4- and 5-cycles going through p). On the other hand they show that AG_n is n-3-fault tolerant vertex 3 pancyclic. In this paper we show that the cycles of length ?6 are much more fault-tolerant. More precisely, we show that AG_n is (2n-6)-fault-tolerant vertex 6 pancyclic. This bound is optimal, because every vertex p has 2n-4 neighbors.     

Fault-tolerant edge and vertex pancyclicity in alternating group graphs

In [J.-M. Chang, J.-S. Yang. Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput. 197 (2008) 760-767] the authors claim that every alternating group graph AG_n is (n − 4)-fault-tolerant edge 4-pancyclic. Which means that if the number of faults ∣F∣ ? n − 4, then every edge in AG_n − F is contained in a cycle of length ?, for every 4 ? ? ? n!/2 − ∣F∣. They also claim that AG_n is (n − 3)-fault-tolerant vertex pancyclic. Which means that if ∣F∣ ? n − 3, then every vertex in AG_n − F is contained in a cycle of length ?, for every 3 ? ? ? n!/2 − ∣F∣. Their proofs are not complete. They left a few important things unexplained. In this paper we fulfill these gaps and present another proofs that AG_n is (n − 4)-fault-tolerant edge 4-pancyclic and (n − 3)-fault-tolerant vertex pancyclic.