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.     

On graphs whose square have strong hamiltonian properties

The squareG² of a graph G is the graph having the same vertex set as G and two vertices are adjacent if and only if they are at distance at most 2 from each other. It is known that if G has no cut-vertex, then G² is Hamilton-connected (see [G. Chartrand, A.M. Hobbs, H.A. Jung, S.F. Kapoor, C.St.J.A. Nash-Williams, The square of a block is hamiltonian connected, J. Combin. Theory Ser. B 16 (1974) 290-292; R.J. Faudree and R.H. Schelp, The square of a block is strongly path connected, J. Combin. Theory Ser. B 20 (1976) 47-61]). We prove that if G has only one cut-vertex, then G² is Hamilton-connected. In the case that G has only two cut-vertices, we prove that if the block that contains the two cut-vertices is hamiltonian, then G² is Hamilton-connected. Further, we characterize all graphs with at most one cycle having Hamilton-connected square.     

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.     

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).     

New results on 3-domination critical graphs

A graph G is said to be 3-domination critical if its domination number γ(G) = 3 and γ(G + e) = 2 for any edge e not contained in G. In this paper we first establish some structural properties of 3-domination critical graphs with diameter equal to 3. In particular, this allows us to characterize a special family of 3-domination critical graphs which contains those with minimum degree one. Moreover, we show that if the minimum degree of a 3-domination critical graph G is at least 3, then α(G) ≤ κ(G) + 1 or G is superconnected, where α(G) is the independence number and κ(G) is the vertex-connectivity of G.     

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].     

A maximum degree theorem for diameter-2-critical graphs

A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ?n ²/4? and that the extremal graphs are the complete bipartite graphs K _?n/2?,?n/2?. Fan [Discrete Math. 67 (1987), 235–240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81–98] proved the conjecture for n > n ₀ where n ₀ is a tower of 2’s of height about 10¹⁴. The conjecture has yet to be proven for other values of n. Let Δ denote the maximum degree of G. We prove the following maximum degree theorems for diameter-2-critical graphs. If Δ ≥ 0.7 n, then the Murty-Simon Conjecture is true. If n ≥ 2000 and Δ ≥ 0.6789 n, then the Murty-Simon Conjecture is true.     

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].].     

Some results related to the toughness of 3-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, even in the special case when the domination number γ=3. In a 1983 paper, Sumner and Blitch proved a theorem which may regarded as a result related to the toughness of 3-γ-critical graphs which says that if S is any vertex cutset of such a graph, then G−S has at most |S|+1 components. In the present paper, we improve and extend this result considerably.     

Remarks on the critical graph conjecture

The vertex-critical graph conjecture (critical graph conjecture respectively) states that every vertex-critical (critical) graph has an odd number of vertices. In this note we prove that if G is a critical graph of even order, then G has at least three vertices of less-than-maximum valency. In addition, if G is a 3-critical multigraph of smallest even order, then G is simple and has no triangles.     

Uniquely pairable graphs

The concept of a k-pairable graph was introduced by Z. Chen [On k-pairable graphs, Discrete Mathematics 287 (2004), 11-15] as an extension of hypercubes and graphs with an antipodal isomorphism. In the present paper we generalize further this concept of a k-pairable graph to the concept of a semi-pairable graph. We prove that a graph is semi-pairable if and only if its prime factor decomposition contains a semi-pairable prime factor or some repeated prime factors. We also introduce a special class of k-pairable graphs which are called uniquely k-pairable graphs. We show that a graph is uniquely pairable if and only if its prime factor decomposition has at least one pairable prime factor, each prime factor is either uniquely pairable or not semi-pairable, and all prime factors which are not semi-pairable are pairwise non-isomorphic. As a corollary we give a characterization of uniquely pairable Cartesian product graphs.     

On <Emphasis Type="Italic">k</Emphasis>-pairable graphs from trees

The concept of the k-pairable graphs was introduced by Zhibo Chen (On k-pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter p(G), called the pair length of a graph G, as the maximum k such that G is k-pairable and p(G) = 0 if G is not k-pairable for any positive integer k. In this paper, we answer the two open questions raised by Chen in the case that the graphs involved are restricted to be trees. That is, we characterize the trees G with p(G) = 1 and prove that p(G □ H) = p(G) + p(H) when both G and H are trees.     

Invalid proofs on incidence coloring

Incidence coloring of a graph G is a mapping from the set of incidences to a color-set C such that adjacent incidences of G are assigned distinct colors. Since 1993, numerous fruitful results as regards incidence coloring have been proved. However, some of them are incorrect. We remedy the error of the proof in [R.A. Brualdi, J.J.Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993) 51-58] concerning complete bipartite graphs. Also, we give an example to show that an outerplanar graph with Δ=4 is not 5-incidence colorable, which contradicts [S.D. Wang, D.L. Chen, S.C. Pang, The incidence coloring number of Halin graphs and outerplanar graphs, Discrete Math. 256 (2002) 397-405], and prove that the incidence chromatic number of the outerplanar graph with Δ≥7 is Δ+1. Moreover, we prove that the incidence chromatic number of the cubic Halin graph is 5. Finally, to improve the lower bound of the incidence chromatic number, we give some sufficient conditions for graphs that cannot be (Δ+1)-incidence colorable.     

Removable edges in a 5-connected graph and a construction method of 5-connected graphs

An edge e of a k-connected graph G is said to be a removable edge if G?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-connected graphs and some properties of quasi k-connected graphs have been investigated [D.A. Holton, B. Jackson, A. Saito, N.C. Wormale, Removable edges in 3-connected graphs, J. Graph Theory 14(4) (1990) 465-473; H. Jiang, J. Su, Minimum degree of minimally quasi (k+1)-connected graphs, J. Math. Study 35 (2002) 187-193; T. Politof, A. Satyanarayana, Minors of quasi 4-connected graphs, Discrete Math. 126 (1994) 245-256; T. Politof, A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Math. 161 (1996) 217-228; J. Su, The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B 75(1) (1999) 74-87; J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems Sci. Math. Sci. 19(4) (1999) 434-438]. In this paper, we first investigate the relation between quasi connectivity and removable edges. Based on the relation, the existence of removable edges in k-connected graphs (k?5) is investigated. It is proved that a 5-connected graph has no removable edge if and only if it is isomorphic to K₆. For a k-connected graph G such that end vertices of any edge of G have at most k-3 common adjacent vertices, it is also proved that G has a removable edge. Consequently, a recursive construction method of 5-connected graphs is established, that is, any 5-connected graph can be obtained from K₆ by a number of θ⁺-operations. We conjecture that, if k is even, a k-connected graph G without removable edge is isomorphic to either K_k+1 or the graph H_k/2+1 obtained from K_k+2 by removing k/2+1 disjoint edges, and, if k is odd, G is isomorphic to K_k+1.     

Independence and connectivity in 3-domination-critical graphs

Let δ, γ, κ and α be, respectively, the minimum degree, the domination number, the connectivity and the independence number of a graph G. The graph G is 3-domination-critical if γ=3 and the addition of any edge decreases γ by 1. In this paper, we prove that if G is a 3-domination-critical graph, then α⩽κ+2; and moreover, if κ⩽δ−1, then α⩽κ+1. We also give a short proof of Wojcicka's result, which says that every connected 3-domination-critical graph of order at least 7 contains a hamiltonian path (J. Graph Theory 14 (1990) 205).     

On a property of minimal triangulations

A graph H has the property MT, if for all graphs G, G is H-free if and only if every minimal (chordal) triangulation of G is H-free. We show that a graph H satisfies property MT if and only if H is edgeless, H is connected and is an induced subgraph of P₅, or H has two connected components and is an induced subgraph of 2P₃.This completes the results of Parra and Scheffler, who have shown that MT holds for H=P_k, the path on k vertices, if and only if k?5 [A. Parra, P. Scheffler, Characterizations and algorithmic applications of chordal graph embeddings, Discrete Applied Mathematics 79 (1997) 171-188], and of Meister, who proved that MT holds for ?P₂, ? copies of a P₂, if and only if ??2 [D. Meister, A complete characterisation of minimal triangulations of 2K₂-free graphs, Discrete Mathematics 306 (2006) 3327-3333].     

Hamiltonicity of 3-Arc Graphs

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v, u, x, y) of vertices such that both (v, u, x) and (u, x, y) are paths of length two. The 3-arc graph of a graph G is defined to have vertices the arcs of G such that two arcs uv, xy are adjacent if and only if (v, u, x, y) is a 3-arc of G. We prove that any connected 3-arc graph is hamiltonian, and all iterative 3-arc graphs of any connected graph of minimum degree at least three are hamiltonian. As a corollary we obtain that any vertex-transitive graph which is isomorphic to the 3-arc graph of a connected arc-transitive graph of degree at least three must be hamiltonian. This confirms the conjecture, for this family of vertex-transitive graphs, that all vertex-transitive graphs with finitely many exceptions are hamiltonian. We also prove that if a graph with at least four vertices is Hamilton-connected, then so are its iterative 3-arc graphs.     

γ-klee-图的Hamilton-连通性和着色

一个r-klee-图递归定义为一个r＋1阶完全图或者通过用一个r阶完全图替换已知的r-klee-图G′中的一个顶点所得到的图.本文主要研究了r-klee-图的Hamilton-连通性和着色问题.我们证明了：每一个r-klee-图是Hamilton-连通的和它的色数是r;如果r是奇数,则它的边色数是r;如果r是偶数,则它的边色数是r＋1.     

R-domination on block graphs

The k-domination problem is to select a minimum cardinality vertex set D of a graph G such that every vertex of G is within distance k from some vertex of D. We consider a generalization of the k-domination problem, called the R-domination problem. A linear algorithm is presented that solves this problem for block graphs. Our algorithm is a generalization of Slater's algorithm [12], which is applicable for forest graphs.     

Domination Defect in Graphs: Guarding With Fewer Guards

In this paper, we introduce a new graph parameter called the domination defect of a graph. The domination number γ of a graph G is the minimum number of vertices required to dominate the vertices of G. Due to the minimality of γ, if a set of vertices of G has cardinality less than γ then there are vertices of G that are not dominated by that set. The k-domination defect of G is the minimum number of vertices which are left un-dominated by a subset of γ - k vertices of G. We study different bounds on the k-domination defect of a graph G with respect to the domination number, order, degree sequence, graph homomorphisms and the existence of efficient dominating sets. We also characterize the graphs whose domination defect is 1 and find exact values of the domination defect for some particular classes of graphs.