Cell rotation graphs of strongly connected orientations of plane graphs with an application

The cell rotation graph D(G) on the strongly connected orientations of a 2-edge-connected plane graph G is defined. It is shown that D(G) is a directed forest and every component is an in-tree with one root; if T is a component of D(G), the reversions of all orientations in T induce a component of D(G), denoted by T⁻, thus (T,T⁻) is called a pair of in-trees of D(G); G is Eulerian if and only if D(G) has an odd number of components (all Eulerian orientations of G induce the same component of D(G)); the width and height of T are equal to that of T⁻, respectively. Further it is shown that the pair of directed tree structures on the perfect matchings of a plane elementary bipartite graph G coincide with a pair of in-trees of D(G). Accordingly, such a pair of in-trees on the perfect matchings of any plane bipartite graph have the same width and height.     

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.     

Feasibility of motion planning on acyclic and strongly connected directed graphs

Motion planning is a fundamental problem of robotics with applications in many areas of computer science and beyond. Its restriction to graphs has been investigated in the literature, for it allows one to concentrate on the combinatorial problem abstracting from geometric considerations. In this paper, we consider motion planning over directed graphs, which are of interest for asymmetric communication networks. Directed graphs generalize undirected graphs, while introducing a new source of complexity to the motion planning problem: moves are not reversible. We first consider the class of acyclic directed graphs and show that the feasibility can be solved in time linear in the product of the number of vertices and the number of arcs. We then turn to strongly connected directed graphs. We first prove a structural theorem for decomposing strongly connected directed graphs into strongly biconnected components. Based on the structural decomposition, we show that the feasibility of motion planning on strongly connected directed graphs can be decided in linear time.     

随机偏好连接图的中心极限定理

我们研究了一类具有随机顶点和边的随机连接图模型, 其中顶点的随机性由一个Poisson 点过程所决定, 边的随机性由一个概率连接函数所决定. 我们得到了带偏好的随机连接图模型的关于所有随机边的长度和的一个中心极限定理.     

Nonseparating trees in 2-connected graphs and oriented trees in strongly connected digraphs

Mader (2010) conjectured that for every positive integer $k$ and every finite tree $T$ with order $m$, every $k$-connected, finite graph $G$ with $\delta \left(G\right)\ge \lfloor \frac{3}{2}k\rfloor +m-1$ contains a subtree $T^{\prime }$ isomorphic to $T$ such that $G-V\left(T^{\prime }\right)$ is $k$-connected. The conjecture has been verified for paths, trees when $k=1$, and stars or double-stars when $k=2$. In this paper we verify the conjecture for two classes of trees when $k=2$.For digraphs, Mader (2012) conjectured that every $k$-connected digraph $D$ with minimum semi-degree $\delta \left(D\right)=min\{{\delta }^{+}\left(D\right),{\delta }^{-}\left(D\right)\}\ge 2k+m-1$ for a positive integer $m$ has a dipath $P$ of order $m$ with $\kappa (D-V\left(P\right))\ge k$. The conjecture has only been verified for the dipath with $m=1$, and the dipath with $m=2$ and $k=1$. In this paper, we prove that every strongly connected digraph with minimum semi-degree $\delta \left(D\right)=min\{{\delta }^{+}\left(D\right),{\delta }^{-}\left(D\right)\}\ge m+1$ contains an oriented tree $T$ isomorphic to some given oriented stars or double-stars with order $m$ such that $D-V\left(T\right)$ is still strongly connected.     

Spectra of strongly Deza graphs

A Deza graph G with parameters $(n,k,b,a)$ is a k-regular graph with n vertices such that any two distinct vertices have b or a common neighbours. The children $G_A$ and $G_B$ of a Deza graph G are defined on the vertex set of G such that every two distinct vertices are adjacent in $G_A$ or $G_B$ if and only if they have a or b common neighbours, respectively. A strongly Deza graph is a Deza graph with strongly regular children. In this paper we give a spectral characterisation of strongly Deza graphs, show relationships between eigenvalues, and study strongly Deza graphs which are distance-regular.     

Hamiltonian connected hourglass free line graphs

Thomassen [Reflections on graph theory, J. Graph Theory 10 (1986) 309-324] conjectured that every 4-connected line graph is hamiltonian. An hourglass is a graph isomorphic to K₅-E(C₄), where C₄ is a cycle of length 4 in K₅. In Broersma et al. [On factors of 4-connected claw-free graphs, J. Graph Theory 37 (2001) 125-136], it is shown that every 4-connected line graph without an induced subgraph isomorphic to the hourglass is hamiltonian connected. In this note, we prove that every 3-connected, essentially 4-connected hourglass free line graph, is hamiltonian connected.     

On signpost systems and connected graphs

By a signpost system we mean an ordered pair (W, P), where W is a finite nonempty set, P W × W × W and the following statements hold: if (u, v, w) P, then (v, u, u) P and (v, u, w) P, for all u, v, w W; if u v; then there exists r W such that (u, r, v) P, for all u, v W. We say that a signpost system (W, P) is smooth if the folowing statement holds for all u, v, x, y, z W: if (u, v, x), (u, v, z), (x, y, z) P, then (u, v, y) P. We say thay a signpost system (W, P) is simple if the following statement holds for all u, v, x, y W: if (u, v, x), (x, y, v) P, then (u, v, y), (x, y, u) P.By the underlying graph of a signpost system (W, P) we mean the graph G with V(G) = W and such that the following statement holds for all distinct u, v W: u and v are adjacent in G if and only if (u, v, v) P. The main result of this paper is as follows: If G is a graph, then the following three statements are equivalent: G is connected; G is the underlying graph of a simple smooth signpost system; G is the underlying graph of a smooth signpost system.Research was supported by Grant Agency of the Czech Republic, grant No. 401/01/0218.     

On the parallel computation of the biconnected and strongly connected co-components of graphs

In this paper, we consider the problems of co-biconnectivity and strong co-connectivity, i.e., computing the biconnected components and the strongly connected components of the complement of a given graph. We describe simple sequential algorithms for these problems, which work on the input graph and not on its complement, and which for a graph on n vertices and m edges both run in optimal O(n+m) time. Our algorithms are not data structure-based and they employ neither breadth-first-search nor depth-first-search.Unlike previous linear co-biconnectivity and strong co-connectivity sequential algorithms, both algorithms admit efficient parallelization. The co-biconnectivity algorithm can be parallelized resulting in an optimal parallel algorithm that runs in time using processors. The strong co-connectivity algorithm can also be parallelized to yield an -time and O(m^1.188/logn)-processor solution. As a byproduct, we obtain a simple optimal O(logn)-time parallel co-connectivity algorithm.Our results show that, in a parallel process environment, the problems of computing the biconnected components and the strongly connected components can be solved with better time-processor complexity on the complement of a graph rather than on the graph itself.     

On bipartite distance-regular graphs with a strongly closed subgraph of diameter three

Let Γ denote a distance-regular graph with a strongly closed regular subgraph Y. Hosoya and Suzuki [R. Hosoya, H. Suzuki, Tight distance-regular graphs with respect to subsets, European J. Combin. 28 (2007) 61-74] showed an inequality for the second largest and least eigenvalues of Γ in the case Y is of diameter 2. In this paper, we study the case when Γ is bipartite and Y is of diameter 3, and obtain an inequality for the second largest eigenvalue of Γ. Moreover, we characterize the distance-regular graphs with a completely regular strongly closed subgraph H(3,2).     

Two‐connected orientations of Eulerian graphs

A graph G = (V, E) is said to be weakly four‐connected if G is 4‐edge‐connected and G – x is 2‐edge‐connected for every x ∈ V. We prove that every weakly four‐connected Eulerian graph has a 2‐connected Eulerian orientation. This verifies a special case of a conjecture of A. Frank . © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 230–242, 2006     

Lifting constructions of strongly regular Cayley graphs

We give two “lifting” constructions of strongly regular Cayley graphs. In the first construction we “lift” a cyclotomic strongly regular graph by using a subdifference set of the Singer difference sets. The second construction uses quadratic forms over finite fields and it is a common generalization of the construction of the affine polar graphs [7] and a construction of strongly regular Cayley graphs given in [15]. The two constructions are related in the following way: the second construction can be viewed as a recursive construction, and the strongly regular Cayley graphs obtained from the first construction can serve as starters for the second construction. We also obtain association schemes from the second construction.     

Ear-decompositions,minimally connected matroids and rigid graphs

We prove that if the two-dimensional rigidity matroid of a graph on at least seven vertices is connected, and is minimal with respect to this property, then has at most edges. This bound, which is best possible, extends Dirac's bound on the size of minimally 2-connected graphs to dimension two. The bound also sharpens the general upper bound of Murty for the size of minimally connected matroids in the case when the matroid is a rigidity matroid of a graph. Our proofs rely on ear-decompositions of connected matroids and on a new lower bound on the size of the largest circuit in a connected rigidity matroid, which may be of independent interest. We use these results to determine the tight upper bound on the number of edges in a minimally redundantly rigid graph in two dimensions. Furthermore, as an application of our proof methods, we give a new proof for Murty's theorem.     

Connectivity keeping paths in k‐connected graphs

A result of G. Chartrand, A. Kaugars, and D. R. Lick [Proc Amer Math Soc 32 (1972), 63–68] says that every finite, k‐connected graph G of minimum degree at least ?3k/2? contains a vertex x such that G?x is still k‐connected. We generalize this result by proving that every finite, k‐connected graph G of minimum degree at least ?3k/2?+m?1 for a positive integer m contains a path P of length m?1 such that G?V(P) is still k‐connected. This has been conjectured in a weaker form by S. Fujita and K. Kawarabayashi [J Combin Theory Ser B 98 (2008), 805–811]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 61–69, 2010.