3-Factor-criticality in domination critical graphs

A graph G is said to be k-γ-critical if the size of any minimum dominating set of vertices is k, but if any edge is added to G the resulting graph can be dominated with k-1 vertices. The structure of k-γ-critical graphs remains far from completely understood when k?3.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G) and is bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G). More generally, a graph is said to be k-factor-critical if G-S has a perfect matching for every set S of k vertices in G. In three previous papers [N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs, Discrete Math. 272 (2003) 5-15; N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs. II. Utilitas Math. 70 (2006) 11-32], we explored the toughness of 3-γ-critical graphs and some of their matching properties. In particular, we obtained some properties which are sufficient for a 3-γ-critical graph to be factor-critical and, respectively, bicritical. In the present work, we obtain similar results for k-factor-critical graphs when k=3.     

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 total domination vertex critical graphs of high connectivity

A graph is called γ-critical if the removal of any vertex from the graph decreases the domination number, while a graph with no isolated vertex is γ_t-critical if the removal of any vertex that is not adjacent to a vertex of degree 1 decreases the total domination number. A γ_t-critical graph that has total domination number k, is called k-γ_t-critical. In this paper, we introduce a class of k-γ_t-critical graphs of high connectivity for each integer k≥3. In particular, we provide a partial answer to the question “Which graphs are γ-critical and γ_t-critical or one but not the other?” posed in a recent work [W. Goddard, T.W. Haynes, M.A. Henning, L.C. van der Merwe, The diameter of total domination vertex critical graphs, Discrete Math. 286 (2004) 255-261].     

Domination critical graphs

A set of vertices S is said to dominate the graph G if for each v ? S, there is a vertex u ∈ S with u adjacent to v. The smallest cardinality of any such dominating set is called the domination number of G and is denoted by γ(G). The purpose of this paper is to initiate an investigation of those graphs which are critical in the following sense: For each v, u ∈ V(G) with v not adjacent to u, γ(G + vu) < γ(G). Thus G is k-y-critical if γ(G) = k and for each edge e ? E(G), γ(G + e) = k ?1. The 2-domination critical graphs are characterized the properties of the k-critical graphs with k ≥ 3 are studied. In particular, the connected 3-critical graphs of even order are shown to have a 1-factor and some stringent restrictions on their degree sequences and diameters are obtained.     

Matching properties in connected domination critical graphs

A dominating set of vertices S of a graph G is connected if the subgraph G[S] is connected. Let γ_c(G) denote the size of any smallest connected dominating set in G. A graph G is k-γ-connected-critical if γ_c(G)=k, but if any edge is added to G, then γ_c(G+e)?k-1. This is a variation on the earlier concept of criticality of edge addition with respect to ordinary domination where a graph G was defined to be k-critical if the domination number of G is k, but if any edge is added to G, the domination number falls to k-1.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G), bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G) or, more generally, k-factor-critical if, for every set S⊆V(G) with |S|=k, the graph G-S contains a perfect matching. In two previous papers [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].] on ordinary (i.e., not necessarily connected) domination, the first and third authors showed that under certain assumptions regarding connectivity and minimum degree, a critical graph G with (ordinary) domination number 3 will be factor-critical (if |V(G)| is odd), bicritical (if |V(G)| is even) or 3-factor-critical (again if |V(G)| is odd). Analogous theorems for connected domination are presented here. Although domination and connected domination are similar in some ways, we will point out some interesting differences between our new results for the case of connected domination and the results in [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].].     

A Characterization of 3-(γ c , 2)-Critical Claw-Free Graphs Which are not 3-γ c -Critical

Let γ _c (G) denote the minimum cardinality of a connected dominating set for G. A graph G is k-γ _c -critical if γ _c (G) = k, but γ _c (G + xy) < k for ${xy \in E(\overline {G})}$ . Further, for integer r ≥ 2, G is said to be k-(γ _c , r)-critical if γ _c (G) = k, but γ _c (G + xy) < k for each pair of non-adjacent vertices x and y that are at distance at most r apart. k-γ _c -critical graphs are k-(γ _c , r)-critical but the converse need not be true. In this paper, we give a characterization of 3-(γ _c , 2)-critical claw-free graphs which are not 3-γ _c -critical. In fact, we show that there are exactly four classes of such graphs.     

Matching Properties in Total Domination Vertex Critical Graphs

A vertex subset S of a graph G = (V,E) is a total dominating set if every vertex of G is adjacent to some vertex in S. The total domination number of G, denoted by γ _t (G), is the minimum cardinality of a total dominating set of G. A graph G with no isolated vertex is said to be total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ _t (G?v) < γ _t (G). A total domination vertex critical graph G is called k-γ _t -critical if γ _t (G) = k. In this paper we first show that every 3-γ _t -critical graph G of even order has a perfect matching if it is K _1,5-free. Secondly, we show that every 3-γ _t -critical graph G of odd order is factor-critical if it is K _1,5-free. Finally, we show that G has a perfect matching if G is a K _1,4-free 4-γ _t (G)-critical graph of even order and G is factor-critical if G is a K _1,4-free 4-γ _t (G)-critical graph of odd order.     

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.     

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.     

Factor-critical property in 3-dominating-critical graphs

A vertex subset S of a graph G is a dominating set if every vertex of G either belongs to S or is adjacent to a vertex of S. The cardinality of a smallest dominating set is called the dominating number of G and is denoted by γ(G). A graph G is said to be γ-vertex-critical if γ(G−v)<γ(G), for every vertex v in G.Let G be a 2-connected K_1,5-free 3-vertex-critical graph of odd order. For any vertex v∈V(G), we show that G−v has a perfect matching (except two graphs), which solves a conjecture posed by Ananchuen and Plummer [N. Ananchuen, M.D. Plummer, Matchings in 3-vertex critical graphs: The odd case, Discrete Math., 307 (2007) 1651-1658].     

Convex Partitions of Graphs

A set of vertices S of a graph G is convex if all vertices of every geodesic between two of its vertices are in S. We say that G is k-convex if V(G) can be partitioned into k convex sets. The convex partition number of G is the least k ⩾ 2 for which G is k-convex. In this paper we examine k-convexity of graphs. We show that it is NP-complete to decide if G is k-convex, for any fixed k ⩾ 2. We describe a characterization for k-convex cographs, leading to a polynomial time algorithm to recognize if a cograph is k-convex. Finally, we discuss k-convexity for disconnected graphs.     

On graphs critical with respect to vertex partition numbers

For k?0, ?_k(G) denotes the Lick-White vertex partition number of G. A graph G is called (n, k)-critical if it is connected and for each edge e of G?_k(G–e)<?_k(G)=n. We describe all (2, k)-critical graphs and for n?3,k?1 we extend and simplify a result of Bollobás and Harary giving one construction of a family of (n, k)-critical graphs of every possible order.     

Total domination dot-stable graphs

A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. Two vertices of G are said to be dotted (identified) if they are combined to form one vertex whose open neighborhood is the union of their neighborhoods minus themselves. We note that dotting any pair of vertices cannot increase the total domination number. Further we show it can decrease the total domination number by at most 2. A graph is total domination dot-stable if dotting any pair of adjacent vertices leaves the total domination number unchanged. We characterize the total domination dot-stable graphs and give a sharp upper bound on their total domination number. We also characterize the graphs attaining this bound.     

A constructive characterization of total domination vertex critical graphs

Let G be a graph of order n and maximum degree Δ(G) and let γ_t(G) denote the minimum cardinality of a total dominating set of a graph G. A graph G with no isolated vertex is the 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. We call these graphs γ_t-critical. For any γ_t-critical graph G, it can be shown that n≤Δ(G)(γ_t(G)−1)+1. In this paper, we prove that: Let G be a connected γ_t-critical graph of order n (n≥3), then n=Δ(G)(γ_t(G)−1)+1 if and only if G is regular and, for each v∈V(G), there is an A⊆V(G)−{v} such that N(v)∩A=0?, the subgraph induced by A is 1-regular, and every vertex in V(G)−A−{v} has exactly one neighbor in A.     

On the Number of Edges in Colour-Critical Graphs and Hypergraphs

A (hyper)graph G is called k-critical if it has chromatic number k, but every proper sub(hyper)graph of it is (k-1)-colourable. We prove that for sufficiently large k, every k-critical triangle-free graph on n vertices has at least (k-o(k))n edges. Furthermore, we show that every (k+1)-critical hypergraph on n vertices and without graph edges has at least (k-3/³?{k}) n(k-3/\sqrt[3]{k}) n edges. Both bounds differ from the best possible bounds by o(kn) even for graphs or hypergraphs of arbitrary girth.     

On the minimal number of edges in color-critical graphs

A graphG isk-critical if it has chromatic numberk, but every proper subgraph of it is (k?1)-colorable. This paper is devoted to investigating the following question: for givenk andn, what is the minimal number of edges in ak-critical graph onn vertices, with possibly some additional restrictions imposed? Our main result is that for everyk≥4 andn>k this number is at least $\left( {\frac{{k - 1}}{2} + \frac{{k - 3}}{{2(k^2 - 2k - 1)}}} \right)n$ , thus improving a result of Gallai from 1963. We discuss also the upper bounds on the minimal number of edges ink-critical graphs and provide some constructions of sparsek-critical graphs. A few applications of the results to Ramsey-type problems and problems about random graphs are described.     

Characterizing defect n-extendable graphs and -critical graphs

A near perfect matching is a matching saturating all but one vertex in a graph. Let G be a connected graph. If any n independent edges in G are contained in a near perfect matching where n is a positive integer and n(|V(G)|-2)/2, then G is said to be defect n-extendable. If deleting any k vertices in G where k|V(G)|-2, the remaining graph has a perfect matching, then G is a k-critical graph. This paper first shows that the connectivity of defect n-extendable graphs can be any integer. Then the characterizations of defect n-extendable graphs and (2k+1)-critical graphs using M-alternating paths are presented.     

Coloring, location and domination of corona graphs

A vertex coloring of a graph G is an assignment of colors to the vertices of G so that every two adjacent vertices of G have different colors. A coloring related property of a graphs is also an assignment of colors or labels to the vertices of a graph, in which the process of labeling is done according to an extra condition. A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those structures of a graph that satisfy some domination property together with other conditions on the vertices of G. In this article we study several mathematical properties related to coloring, domination and location of corona graphs. We investigate the distance-k colorings of corona graphs. Particularly, we obtain tight bounds for the distance-2 chromatic number and distance-3 chromatic number of corona graphs, through some relationships between the distance-k chromatic number of corona graphs and the distance-k chromatic number of its factors. Moreover, we give the exact value of the distance-k chromatic number of the corona of a path and an arbitrary graph. On the other hand, we obtain bounds for the Roman dominating number and the locating–domination number of corona graphs. We give closed formulaes for the k-domination number, the distance-k domination number, the independence domination number, the domatic number and the idomatic number of corona graphs.     

On 3-Steiner simplicial orderings

Let G be a connected graph and S a nonempty set of vertices of G. A Steiner tree for S is a connected subgraph of G containing S that has a minimum number of edges. The Steiner interval for S is the collection of all vertices in G that belong to some Steiner tree for S. Let k≥2 be an integer. A set X of vertices of G is k-Steiner convex if it contains the Steiner interval of every set of k vertices in X. A vertex x∈X is an extreme vertex of X if X?{x} is also k-Steiner convex. We call such vertices k-Steiner simplicial vertices. We characterize vertices that are 3-Steiner simplicial and give characterizations of two classes of graphs, namely the class of graphs for which every ordering produced by Lexicographic Breadth First Search is a 3-Steiner simplicial ordering and the class for which every ordering of every induced subgraph produced by Maximum Cardinality Search is a 3-Steiner simplicial ordering.