Distance connectivity in graphs and digraphs

Let G = (V, A) be a digraph with diameter D ≠ 1. For a given integer 2 ≤ t ≤ D, the t-distance connectivity κ(t) of G is the minimum cardinality of an x → y separating set over all the pairs of vertices x, y which are at distance d(x, y) ≥ t. The t-distance edge connectivity λ(t) of G is defined similarly. The t-degree of G, δ(t), is the minimum among the out-degrees and in-degrees of all vertices with (out- or -in-) eccentricity at least t. A digraph is said to be maximally distance connected if κ(t) = δ(t) for all values of t. In this paper we give a construction of a digraph having D − 1 positive arbitrary integers c₂ ≤ … ≤ c_D, D > 3, as the values of its t-distance connectivities κ(2) = c₂, …, κ(D) = c_D. Besides, a digraph that shows the independence of the parameters κ(t), λ(t), and δ(t) is constructed. Also we derive some results on the distance connectivities of digraphs, as well as sufficient conditions for a digraph to be maximally distance connected. Similar results for (undirected) graphs are presented. © 1996 John Wiley & Sons, Inc.     

On the connectivity of randomm-orientable graphs and digraphs

We consider graphs and digraphs obtained by randomly generating a prescribed number of arcs incident at each vertex. We analyse their almost certain connectivity and apply these results to the expected value of random minimum length spanning trees and arborescences. We also examine the relationship between our results and certain results of Erdős and Rényi.     

Size of graphs and digraphs with given diameter and connectivity constraints

Acta Mathematica Hungarica - We determine the maximum size of a graph of given order, diameter, and edge-connectivity $$lambda$$ for $$2leq lambda leq 7$$ . This completes the determination of...     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.     

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.     

Eigenvalues of graphs and digraphs

We show that given a digraph X there is a vertex-transitive digraph Y such that the minimal polynomial of X divides that of Y. Two consequences of this are that there exist vertex-transitive digraphs with nondiagonalizable adjacency matrices and that any algebraic integer is the eigenvalue of some vertex-transitive digraph.     

The strong metric dimension of graphs and digraphs

Let G be a connected (di)graph. A vertex w is said to strongly resolve a pair u,v of vertices of G if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set W of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of W. The smallest cardinality of a strong resolving set for G is called the strong dimension of G. It is shown that the problem of finding the strong dimension of a connected graph can be transformed to the problem of finding the vertex covering number of a graph. Moreover, it is shown that computing this invariant is NP-hard. Related invariants for directed graphs are defined and studied.     

Derangement action digraphs and graphs

A derangement of a set $X$ is a fixed-point-free permutation of $X$. Derangement action digraphs are closely related to group action digraphs introduced by Annexstein, Baumslag and Rosenberg in 1990. For a non-empty set $X$ and a non-empty subset $S$ of derangements of $X$, the derangement action digraph $\overrightarrow{DA}(X,S)$ has vertex set $X$, and an arc from $x$ to $y$ if and only if $y$ is the image of $x$ under the action of some element of $S$, so by definition it is a simple digraph. In common with Cayley graphs and Cayley digraphs, derangement action digraphs may be useful to model networks since the same routing and communication schemes can be implemented at each vertex. We prove that the family of derangement action digraphs contains all Cayley digraphs, all finite vertex-transitive simple graphs, and all finite regular simple graphs of even valency. We determine necessary and sufficient conditions on $S$ under which $\overrightarrow{DA}(X,S)$ may be viewed as a simple undirected graph of valency $\left|S\right|$. We investigate structural and symmetry properties of these digraphs and graphs, pose several open problems, and give many examples.     

Arbitrarily traceable graphs and digraphs

The work in this paper extends and generalizes earlier work by Ore on arbitrarily traceable Euler graphs, by Harary on arbitrarily traceable digraphs, by Chartrand and White on randomly n-traversable graphs, and by Chartrand and Lick on randomly Eulerian digraphs. Arbitrarily traceable graphs of mixed type are defined and characterized in terms of a class of forbidden graphs. Arbitrarily traceable digraphs of mixed type are also defined and a simply applied characterization is given for them.     

Ferrers digraphs and threshold graphs

We deduce a set of known characterizations of threshold graphs (Theorem 3) from a set of characterizations of Ferrers digraphs (Theorem 1) by investigating the connection between symmetric Ferrers digraphs and threshold graphs. A direct proof of Theorem 3 is easier than the one provided in here, but the purpose of this paper is to view Theorem 1 as an extension of Theorem 3 to the directed case (this extension point of view still holds on an algorithmic ground).     

Degree and local connectivity in digraphs

It is shown that there is a digraphD of minimum outdegree 12m and μ(x, y; D)=11m, but every digraphD of minimum outdegreen contains verticesx ≠y withλ(x, y; D)≧n−1, whereμ(x, y; D) andλ(x, y; D) denote the maximum number of openly disjoint and edge-disjoint paths, respectively.     

Subgraphs of large connectivity and chromatic number in graphs of large chromatic number

For each pair k, m of natural numbers there exists a natural number f(k, m) such that every f(k, m)-chromatic graph contains a k-connected subgraph of chromatic number at least m.     

Isomorphism of circulant graphs and digraphs

Let S? {1, …, n?1} satisfy ?S = S mod n. The circulant graph G(n, S) with vertex set {v₀, v₁,…, v_n?1} and edge set E satisfies v_iv_j?E if and only if j ? i ∈ S, where all arithmetic is done mod n. The circulant digraph G(n, S) is defined similarly without the restriction S = ? S. Ádám conjectured that $\text{G(n, S) ? G(n, S′)}$ if and only if S = uS′ for some unit u mod n. In this paper we prove the conjecture true if n = pq where p and q are distinct primes. We also show that it is not generally true when n = p², and determine exact conditions on S that it be true in this case. We then show as a simple consequence that the conjecture is false in most cases when n is divisible by p² where p is an odd prime, or n is divisible by 2⁴.     

Fundamental groupoids of digraphs and graphs

We introduce the notion of fundamental groupoid of a digraph and prove its basic properties. In particular, we obtain a product theorem and an analogue of the Van Kampen theorem. Considering the category of (undirected) graphs as the full subcategory of digraphs, we transfer the results to the category of graphs. As a corollary we obtain the corresponding results for the fundamental groups of digraphs and graphs. We give an application to graph coloring.     

The chromatic connectivity of graphs

A graphG ischromatically k-connected if every vertex cutset induces a subgraph with chromatic number at leastk. This concept arose in some work, involving the third author, on Ramsey Theory. (For the reference, see the text.) Here we begin the study of chromatic connectivity for its own sake. We show thatG is chromaticallyk-connected iff every homomorphic image of it isk-connected. IfG has no triangles then it is at most chromatically 1-connected, but we prove that the Kneser graphs provide examples ofK ₄-free graphs with arbitrarily large chromatic connectivity. We also verify thatK ₄-free planar graphs are at most chromatically 2-connected.This work was supported by grants from NSERC of Canada.     

The connectivity of commuting graphs

A necessary and sufficient condition is proven for the connectivity of commuting graphs C(G,X), where G is Sym(n), the symmetric group of degree n, and X is any G-conjugacy class.     

Large butterfly Cayley graphs and digraphs

We present families of large undirected and directed Cayley graphs whose construction is related to butterfly networks. One approach yields, for every large $k$ and for values of $d$ taken from a large interval, the largest known Cayley graphs and digraphs of diameter $k$ and degree $d$. Another method yields, for sufficiently large $k$ and infinitely many values of $d$, Cayley graphs and digraphs of diameter $k$ and degree $d$ whose order is exponentially larger in $k$ than any previously constructed. In the directed case, these are within a linear factor in $k$ of the Moore bound.