Codiameters of 3-domination critical graphs with toughness more than one

A graph G is 3-domination-critical (3-critical, for short), if its domination number γ is 3 and the addition of any edge decreases γ by 1. In this paper, we show that every 3-critical graph with independence number 4 and minimum degree 3 is Hamilton-connected. Combining the result with those in [Y.J. Chen, F. Tian, B. Wei, Hamilton-connectivity of 3-domination critical graphs with α≤δ, Discrete Mathematics 271 (2003) 1-12; Y.J. Chen, F. Tian, Y.Q. Zhang, Hamilton-connectivity of 3-domination critical graphs with α=δ+2, European Journal of Combinatorics 23 (2002) 777-784; Y.J. Chen, T.C.E. Cheng, C.T. Ng, Hamilton-connectivity of 3-domination critical graphs with α=δ+1≥5, Discrete Mathematics 308 (2008) (in press)], we solve the following conjecture: a connected 3-critical graph G is Hamilton-connected if and only if τ(G)>1, where τ(G) is the toughness of G.     

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.     

On the total domination subdivision numbers in graphs

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_γt (G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Karami, Khoeilar, Sheikholeslami and Khodkar, (Graphs and Combinatorics, 2009, 25, 727–733) proved that for any connected graph G of order n ≥ 3, sd_{γ t} (G) ≤ 2γ _t (G) − 1 and posed the following problem: Characterize the graphs that achieve the aforementioned upper bound. In this paper we first prove that sd_{γ t} (G) ≤ 2α′(G) for every connected graph G of order n ≥ 3 and δ(G) ≥ 2 where α′(G) is the maximum number of edges in a matching in G and then we characterize all connected graphs G with sd_{γ t} (G)=2γ _t (G)−1.     

Super Connectivity and Super Edge Connectivity of the Mycielskian of a Graph

Mycielski introduced a new graph transformation μ(G) for graph G, which is called the Mycielskian of G. A graph G is super connected or simply super-κ (resp. super edge connected or super-λ), if every minimum vertex cut (resp. minimum edge cut) isolates a vertex of G. In this paper, we show that for a connected graph G with |V(G)| ≥ 2, μ(G) is super-κ if and only if δ(G) < 2κ(G), and μ(G) is super-λ if and only if G\ncong K₂{G\ncong K_2}.     

Diameter-vital edges in a graph

The graph resulting from contracting edge e is denoted as G/e and the graph resulting from deleting edge e is denoted as G − e. An edge e is diameter-essential if diam(G/e) < diam(G), diameter-increasing if diam(G − e) < diam(G), and diameter-vital if it is both diameter-essential and diameter-increasing. We partition the edges that are not diameter-vital into three categories. In this paper, we study realizability questions relating to the number of edges that are not diameter-vital in the three defined categories. A graph is diameter-vital if all its edges are diameter-vital. We give a structural characterization of diameter-vital graphs.     

Total Restrained Domination in Cubic Graphs

A set S of vertices in a graph G = (V, E) is a total restrained dominating set (TRDS) of G if every vertex of G is adjacent to a vertex in S and every vertex of V − S is adjacent to a vertex in V − S. The total restrained domination number of G, denoted by γ _tr (G), is the minimum cardinality of a TRDS of G. Let G be a cubic graph of order n. In this paper we establish an upper bound on γ _tr (G). If adding the restriction that G is claw-free, then we show that γ _tr (G) = γ _t (G) where γ _t (G) is the total domination number of G, and thus some results on total domination in claw-free cubic graphs are valid for total restrained domination. Research was partially supported by the NNSF of China (Nos. 60773078, 10832006), the ShuGuang Plan of Shanghai Education Development Foundation (No. 06SG42) and Shanghai Leading Academic Discipline Project (No. S30104).     

Degree Sums,Connectivity and Dominating Cycles in Graphs

Let G be a graph of order n with connectivity κ≥3 and let α be the independence number of G. Set σ₄(G)= min{∑⁴ _{i =1} d(x _i ):{x ₁,x ₂,x ₃,x ₄} is an independent set of G}. In this paper, we will prove that if σ₄(G)≥n+2κ, then there exists a longest cycle C of G such that V(G−C) is an independent set of G. Furthermore, if the minimum degree of G is at least α, then G is hamiltonian. Received: July 31, 1998?Final version received: October 4, 2000     

On the Roman Bondage Number of Planar Graphs

A Roman dominating function on a graph G is a function f : V(G) → {0, 1, 2} satisfying the condition that every vertex u for which f (u) = 0 is adjacent to at least one vertex v for which f (v) = 2. The weight of a Roman dominating function is the value f (V(G)) = ?_{u ? V(G)} f (u){f (V(G)) = \sum_{u\in V(G)} f (u)}. The Roman domination number, γ _R (G), of G is the minimum weight of a Roman dominating function on G. The Roman bondage number b _R (G) of a graph G with maximum degree at least two is the minimum cardinality of all sets E^￠ í E(G){E^{\prime} \subseteq E(G)} for which γ _R (G − E′) > γ _R (G). In this paper we present different bounds on the Roman bondage number of planar graphs.     

Paired Domination Vertex Critical Graphs

Let γ _pr (G) denote the paired domination number of graph G. A graph G with no isolated vertex is paired domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ _pr (G – v) < γ _pr (G). We call these graphs γ _pr -critical. In this paper, we present a method of constructing γ _pr -critical graphs from smaller ones. Moreover, we show that the diameter of a γ _pr -critical graph is at most and the upper bound is sharp, which answers a question proposed by Henning and Mynhardt [The diameter of paired-domination vertex critical graphs, Czechoslovak Math. J., to appear]. Xinmin Hou: Research supported by NNSF of China (No.10701068 and No.10671191).     

There Exist Highly Critically Connected Graphs of Diameter Three

Let κ(G) denote the (vertex) connectivity of a graph G. For ℓ≥0, a noncomplete graph of finite connectivity is called ℓ-critical if κ(G−X)=κ(G)−|X| for every X⊆V(G) with |X|≤ℓ. Mader proved that every 3-critical graph has diameter at most 4 and asked for 3-critical graphs having diameter exceeding 2. Here we give an affirmative answer by constructing an ℓ-critical graph of diameter 3 for every ℓ≥3.     

List Point Arboricity of Dense Graphs

Let G be a simple graph. The point arboricity ρ(G) of G is defined as the minimum number of subsets in a partition of the point set of G so that each subset induces an acyclic subgraph. The list point arboricity ρ _l (G) is the minimum k so that there is an acyclic L-coloring for any list assignment L of G which |L(v)| ≥ k. So ρ(G) ≤ ρ _l (G) for any graph G. Xue and Wu proved that the list point arboricity of bipartite graphs can be arbitrarily large. As an analogue to the well-known theorem of Ohba for list chromatic number, we obtain ρ _l (G + K _n ) = ρ(G + K _n ) for any fixed graph G when n is sufficiently large. As a consequence, if ρ(G) is close enough to half of the number of vertices in G, then ρ _l (G) = ρ(G). Particularly, we determine that , where K _2(n) is the complete n-partite graph with each partite set containing exactly two vertices. We also conjecture that for a graph G with n vertices, if then ρ _l (G) = ρ(G). Research supported by NSFC (No.10601044) and XJEDU2006S05.     

A Sharp Upper Bound for the Number of Spanning Trees of a Graph

Let G = (V,E) be a simple graph with n vertices, e edges and d₁ be the highest degree. Further let λ_i, i = 1,2,...,n be the non-increasing eigenvalues of the Laplacian matrix of the graph G. In this paper, we obtain the following result: For connected graph G, λ₂ = λ₃ = ... =  λ_n-1 if and only if G is a complete graph or a star graph or a (d₁,d₁) complete bipartite graph. Also we establish the following upper bound for the number of spanning trees of G on n, e and d₁ only:

Minimum degree of minimal defect -extendable bipartite graphs

A near perfect matching is a matching saturating all but one vertex in a graph. If G is a connected graph and any n independent edges in G are contained in a near perfect matching, then G is said to be defect n-extendable. If for any edge e in a defect n-extendable graph G, G−e is not defect n-extendable, then G is minimal defect n-extendable. The minimum degree and the connectivity of a graph G are denoted by δ(G) and κ(G) respectively. In this paper, we study the minimum degree of minimal defect n-extendable bipartite graphs. We prove that a minimal defect 1-extendable bipartite graph G has δ(G)=1. Consider a minimal defect n-extendable bipartite graph G with n≥2, we show that if κ(G)=1, then δ(G)≤n+1 and if κ(G)≥2, then 2≤δ(G)=κ(G)≤n+1. In addition, graphs are also constructed showing that, in all cases but one, there exist graphs with minimum degree that satisfies the established bounds.     

Bounds on the Total Restrained Domination Number of a Graph

Let G = (V, E) be a graph. A set S í V{S \subseteq V} is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V − S is adjacent to a vertex in V − S. The total restrained domination number of G, denoted by γ _tr (G), is the smallest cardinality of a total restrained dominating set of G. We show that if δ ≥ 3, then γ _tr (G) ≤ n − δ − 2 provided G is not one of several forbidden graphs. Furthermore, we show that if G is r − regular, where 4 ≤ r ≤ n − 3, then γ _tr (G) ≤ n − diam(G) − r + 1.     

On hamiltonicity of <Emphasis Type="Italic">P</Emphasis><Subscript>3</Subscript>-dominated graphs

We introduce a new class of graphs which we call P ₃-dominated graphs. This class properly contains all quasi-claw-free graphs, and hence all claw-free graphs. Let G be a 2-connected P ₃-dominated graph. We prove that G is hamiltonian if α(G ²) ≤ κ(G), with two exceptions: K _2,3 and K _1,1,3. We also prove that G is hamiltonian, if G is 3-connected and |V(G)| ≤ 5δ(G) − 5. These results extend known results on (quasi-)claw-free graphs. This paper was completed when both authors visited the Center for Combinatorics, Nankai University, Tianjin. They gratefully acknowledge the hospitality and support of the Center for Combinatorics and Nankai University. The work of E.Vumar is sponsored by SRF for ROCS, REM.     

Almost 2-Homogeneous Graphs and Completely Regular Quadrangles

Many known distance-regular graphs have extra combinatorial regularities: One of them is t-homogeneity. A bipartite or almost bipartite distance-regular graph is 2-homogeneous if the number γ _i  = |{x | ∂(u, x) = ∂(v, x) = 1 and ∂(w, x) = i − 1}| (i = 2, 3,..., d) depends only on i whenever ∂(u, v) = 2 and ∂(u, w) = ∂(v, w) = i. K. Nomura gave a complete classification of bipartite and almost bipartite 2-homogeneous distance-regular graphs. In this paper, we generalize Nomura’s results by classifying 2-homogeneous triangle-free distance-regular graphs. As an application, we show that if Γ is a distance-regular graph of diameter at least four such that all quadrangles are completely regular then Γ is isomorphic to a binary Hamming graph, the folded graph of a binary Hamming graph or the coset graph of the extended binary Golay code of valency 24. We also consider the case Γ is a parallelogram-free distance-regular graph. This research was partially supported by the Grant-in-Aid for Scientific Research (No.17540039), Japan Society of the Promotion of Science.     

Disproof of a Conjecture on the Subdivision Domination Number of a Graph

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. The domination subdivision number sd_γ(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Haynes et al. (Discussiones Mathematicae Graph Theory 21 (2001) 239-253) conjectured that for any graph G with . In this note we first give a counterexample to this conjecture in general and then we prove it for a particular class of graphs.     

A bound on the <Emphasis Type="Italic">k</Emphasis>-domination number of a graph

Let G be a graph with vertex set V(G), and let k ⩾ 1 be an integer. A subset D ⊆ V(G) is called a k-dominating set if every vertex υ ∈ V(G)-D has at least k neighbors in D. The k-domination number γ _k (G) of G is the minimum cardinality of a k-dominating set in G. If G is a graph with minimum degree δ(G) ⩾ k + 1, then we prove that

Paired-Domination Subdivision Numbers of Graphs

A paired-dominating set of a graph G = (V, E) 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 paired-domination subdivision number sd _γpr (G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the paired-domination number. In this paper we establish upper bounds on the paired-domination subdivision number and pose some problems and conjectures.     

On signed distance-k-domination in graphs

The signed distance-k-domination number of a graph is a certain variant of the signed domination number. If v is a vertex of a graph G, the open k-neighborhood of v, denoted by N _k (v), is the set N _k (v) = {u: u ≠ v and d(u, v) ⩽ k}. N _k [v] = N _k (v) ⋃ {v} is the closed k-neighborhood of v. A function f: V → {−1, 1} is a signed distance-k-dominating function of G, if for every vertex . The signed distance-k-domination number, denoted by γ _k,s (G), is the minimum weight of a signed distance-k-dominating function on G. The values of γ _2,s (G) are found for graphs with small diameter, paths, circuits. At the end it is proved that γ _2,s (T) is not bounded from below in general for any tree T.