The diameter of paired-domination vertex critical graphs

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γ _pr(G), is the minimum cardinality of a paired-dominating set of G. The graph G is paired-domination vertex critical if for every vertex v of G that is not adjacent to a vertex of degree one, γ _pr(G − v) < γ _pr(G). We characterize the connected graphs with minimum degree one that are paired-domination vertex critical and we obtain sharp bounds on their maximum diameter. We provide an example which shows that the maximum diameter of a paired-domination vertex critical graph is at least 3/2 (γ _pr(G) − 2). For γ _pr(G) ⩽ 8, we show that this lower bound is precisely the maximum diameter of a paired-domination vertex critical graph. The first author was supported in part by the South African National Research Foundation and the University of KwaZulu-Natal, the second author was supported by the Natural Sciences and Engineering Research Council of Canada.     

The diameter of total domination vertex critical graphs

A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G-v is less than the total domination number of G. These graphs we call γ_t-critical. If such a graph G has total domination number k, we call it k-γ_t-critical. We characterize the connected graphs with minimum degree one that are γ_t-critical and we obtain sharp bounds on their maximum diameter. We calculate the maximum diameter of a k-γ_t-critical graph for k?8 and provide an example which shows that the maximum diameter is in general at least 5k/3-O(1).     

On color critical graphs

It is shown that the minimal number of edges which have to be omitted from a (k + 1)-critical graph on n vertices in order to make it bipartite is at least ^k₂ for n large enough. This bound is best possible. Various related questions are considered.     

On list critical graphs

In this paper we discuss some basic properties of k-list critical graphs. A graph G is k-list critical if there exists a list assignment L for G with |L(v)|=k−1 for all vertices v of G such that every proper subgraph of G is L-colorable, but G itself is not L-colorable. This generalizes the usual definition of a k-chromatic critical graph, where L(v)={1,…,k−1} for all vertices v of G. While the investigation of k-critical graphs is a well established part of coloring theory, not much is known about k-list critical graphs. Several unexpected phenomena occur, for instance a k-list critical graph may contain another one as a proper induced subgraph, with the same value of k. We also show that, for all 2≤p≤k, there is a minimal k-list critical graph with chromatic number p. Furthermore, we discuss the question, for which values of k and n is the complete graph K_nk-list critical. While this is the case for all 5≤k≤n, K_n is not 4-list critical if n is large.     

On the diameter of Kronecker graphs

We prove that a.a.s. as soon as a Kronecker graph becomes connected it has a finite diameter.     

On the diameter of generalized Kneser graphs

Let r, k be positive integers, s(<r), a nonnegative integer, and n=2r-s+k. The set of r-subsets of [n]={1,2,…,n} is denoted by [n]^r. The generalized Kneser graph K(n,r,s) is the graph whose vertex-set is [n]^r where two r-subsets A and B are joined by an edge if |A∩B|?s. This note determines the diameter of generalized Kneser graphs. More precisely, the diameter of K(n,r,s) is equal to , which generalizes a result of Valencia-Pabon and Vera [On the diameter of Kneser graphs, Discrete Math. 305 (2005) 383-385].     

On global domination critical graphs

A dominating set of a graph G=(V,E) is a subset S⊆V such that every vertex not in S is adjacent to at least one vertex of S. The domination number of G is the cardinality of a smallest dominating set. The global domination number, γ_g(G), is the cardinality of a smallest set S that is simultaneously a dominating set of both G and its complement . Graphs for which γ_g(G−e)>γ_g(G) for all edges e∈E are characterized, as are graphs for which γ_g(G−e)<γ_g(G) for all edges e∈E whenever is disconnected. Progress is reported in the latter case when is connected.     

Strengthening the Murty–Simon conjecture on diameter 2 critical graphs

A graph is diameter-2-critical if its diameter is 2 but the removal of any edge increases the diameter. A well-studied conjecture, known as the Murty–Simon conjecture, states that any diameter-2-critical graph of order $n$ has at most $?n^2∕4?$ edges, with equality if and only if $G$ is a balanced complete bipartite graph. Many partial results about this conjecture have been obtained, in particular it is known to hold for all sufficiently large graphs, for all triangle-free graphs, and for all graphs with a dominating edge. In this paper, we discuss ways in which this conjecture can be strengthened. Extending previous conjectures in this direction, we conjecture that, when we exclude the class of complete bipartite graphs and one particular graph, the maximum number of edges of a diameter-2-critical graph is at most $?{(n?1)}^2∕4?+1$. The family of extremal examples is conjectured to consist of certain twin-expansions of the 5-cycle (with the exception of a set of thirteen special small graphs). Our main result is a step towards our conjecture: we show that the Murty–Simon bound is not tight for non-bipartite diameter-2-critical graphs that have a dominating edge, as they have at most $?n^2∕4??2$ edges. Along the way, we give a shorter proof of the Murty–Simon conjecture for this class of graphs, and stronger bounds for more specific cases. We also characterize diameter-2-critical graphs of order $n$ with maximum degree $n?2$: they form an interesting family of graphs with a dominating edge and $2n?4$ edges.     

On the critical ideals of graphs

We introduce some determinantal ideals of the generalized Laplacian matrix associated to a digraph G, that we call critical ideals of G. Critical ideals generalize the critical group and the characteristic polynomials of the adjacency and Laplacian matrices of a digraph. The main results of this article are the determination of some minimal generator sets and the reduced Gröbner basis for the critical ideals of the complete graphs, the cycles and the paths. Also, we establish a bound between the number of trivial critical ideals and the stability and clique numbers of a graph.     

On bipartite graphs of diameter 3 and defect 2

We consider bipartite graphs of degree Δ≥2, diameter D=3, and defect 2 (having 2 vertices less than the bipartite Moore bound). Such graphs are called bipartite (Δ, 3, ?2) ‐graphs. We prove the uniqueness of the known bipartite (3, 3, ?2) ‐graph and bipartite (4, 3, ?2)‐graph. We also prove several necessary conditions for the existence of bipartite (Δ, 3, ?2) ‐graphs. The most general of these conditions is that either Δ or Δ?2 must be a perfect square. Furthermore, in some cases for which the condition holds, in particular, when Δ=6 and Δ=9, we prove the non‐existence of the corresponding bipartite (Δ, 3, ?2)‐graphs, thus establishing that there are no bipartite (Δ, 3, ?2)‐graphs, for 5≤Δ≤10. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 271–288, 2009     

On the girth and diameter of generalized Johnson graphs

Let $v>k>i$ be non-negative integers. The generalized Johnson graph, $J(v,k,i)$, is the graph whose vertices are the $k$-subsets of a $v$-set, where vertices $A$ and $B$ are adjacent whenever $|A\cap B|=i$. In this article, we derive general formulas for the girth and diameter of $J(v,k,i)$. Additionally, we provide a formula for the distance between any two vertices $A$ and $B$ in terms of the cardinality of their intersection.     

On the size of Edge-Chromatic critical graphs

A conjecture of V.G. Vizing states that if G is a Δ-critical graph of order ? and size m, thenm ≥ 1/2(n(Δ - 1) + 3). This conjecture has been verified for Δ ≤ 4 by I.T. Jakobsen, L.W. Beineke, S. Fiorini and H.P. Yap. In this paper, we prove the conjecture for Δ = 5.     

On critical graphs with chromatic index 4

It is shown that the number of vertices of valency 2 in a critical graph with chromatic index 4 is at most 1/3 of the total number of vertices, and that there exist critical graphs with just one vertex of valency 2, but none with exactly two vertices of valency 2. From this bounds for the number of edges are deduced. The paper ends with a presentation of a catalogue of all critical graphs with chromatic index 4 and at most 8 vertices, and all simple critical graphs with chromatic index 4 and at most 10 vertices.     

On the connectivity and superconnected graphs with small diameter

In this paper, first we prove that any graph G is 2-connected if diam(G)≤g−1 for even girth g, and for odd girth g and maximum degree Δ≤2δ−1 where δ is the minimum degree. Moreover, we prove that any graph G of diameter diam(G)≤g−2 satisfies that (i) G is 5-connected for even girth g and Δ≤2δ−5, and (ii) G is super-κ for odd girth g and Δ≤3δ/2−1.