Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs

Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by d_G(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, d_H(S)=d_G(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed.     

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.     

The insulation sequence of a graph

In a graph G, a k-insulated set S is a subset of the vertices of G such that every vertex in S is adjacent to at most k vertices in S, and every vertex outside S is adjacent to at least k+1 vertices in S. The insulation sequencei₀,i₁,i₂,… of a graph G is defined by setting i_k equal to the maximum cardinality of a k-insulated set in G. We determine the insulation sequence for paths, cycles, fans, and wheels. We also study the effect of graph operations, such as the disjoint union, the join, the cross product, and graph composition, upon k-insulated sets. Finally, we completely characterize all possible orderings of the insulation sequence, and prove that the insulation sequence is increasing in trees.     

The 3-choosability of plane graphs of girth 4

A set S of vertices of the graph G is called k-reducible if the following is true: G is k-choosable if and only if G-S is k-choosable. A k-reduced subgraphH of G is a subgraph of G such that H contains no k-reducible set of some specific forms. In this paper, we show that a 3-reduced subgraph of a non-3-choosable plane graph G contains either adjacent 5-faces, or an adjacent 4-face and k-face, where k?6. Using this result, we obtain some sufficient conditions for a plane graph to be 3-choosable. In particular, if G is of girth 4 and contains no 5- and 6-cycles, then G is 3-choosable.     

Edge-connectivity and edge-superconnectivity in sequence graphs

Given an integer k?1 and any graph G, the sequence graph S_k(G) is the graph whose set of vertices is the set of all walks of length k in G. Moreover, two vertices of S_k(G) are joined by an edge if and only if their corresponding walks are adjacent in G.In this paper we prove sufficient conditions for a sequence graph S_k(G) to be maximally edge-connected and edge-superconnected depending on the parity of k and on the vertex-connectivity of the original graph G.     

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.     

Total domination changing and stable graphs upon vertex removal

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. A graph is total domination vertex removal stable if the removal of an arbitrary vertex leaves the total domination number unchanged. On the other hand, a graph is total domination vertex removal changing if the removal of an arbitrary vertex changes the total domination number. In this paper, we study total domination vertex removal changing and stable graphs.     

Total domination critical and stable graphs upon edge removal

A set S of vertices in a graph G is a total dominating set of G 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. A graph is total domination edge critical if the removal of any arbitrary edge increases the total domination number. On the other hand, a graph is total domination edge stable if the removal of any arbitrary edge has no effect on the total domination number. In this paper, we characterize total domination edge critical graphs. We also investigate various properties of total domination edge stable graphs.     

Spanning Star Trees in Regular Graphs

For a subset W of vertices of an undirected graph G, let S(W) be the subgraph consisting of W, all edges incident to at least one vertex in W, and all vertices adjacent to at least one vertex in W. If S(W) is a tree containing all the vertices of G, then we call it a spanning star tree of G. In this case W forms a weakly connected but strongly acyclic dominating set for G. We prove that for every r ≥ 3, there exist r-regular n-vertex graphs that have spanning star trees, and there exist r-regular n-vertex graphs that do not have spanning star trees, for all n sufficiently large (in terms of r). Furthermore, the problem of determining whether a given regular graph has a spanning star tree is NP-complete.     

Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs

A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=I[u,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?_u,v∈SI[u,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph.     

On geodetic sets formed by boundary vertices

Let G be a finite simple connected graph. A vertex v is a boundary vertex of G if there exists a vertex u such that no neighbor of v is further away from u than v. We obtain a number of properties involving different types of boundary vertices: peripheral, contour and eccentric vertices. Before showing that one of the main results in [G. Chartrand, D. Erwin, G.L. Johns, P. Zhang, Boundary vertices in graphs, Discrete Math. 263 (2003) 25-34] does not hold for one of the cases, we establish a realization theorem that not only corrects the mentioned wrong statement but also improves it.Given S⊆V(G), its geodetic closure I[S] is the set of all vertices lying on some shortest path joining two vertices of S. We prove that the boundary vertex set ∂(G) of any graph G is geodetic, that is, I[∂(G)]=V(G). A vertex v belongs to the contour Ct(G) of G if no neighbor of v has an eccentricity greater than v. We present some sufficient conditions to guarantee the geodeticity of either the contour Ct(G) or its geodetic closure I[Ct(G)].     

Random mappings of scaled graphs

Given a connected finite graph Γ with a fixed base point O and some graph G with a based point we study random 1-Lipschitz maps of a scaled Γ into G. We are mostly interested in the case where G is a Cayley graph of some finitely generated group, where the construction does not depend on the choice of base points. A particular case of Γ being a graph on two vertices and one edge corresponds to the random walk on G, and the case where Γ is a graph on two vertices and two edges joining them corresponds to Brownian bridge in G. We show, that unlike in the case ${G=\mathbb Z^d}$ , the asymptotic behavior of a random scaled mapping of Γ into G may differ significantly from the asymptotic behavior of random walks or random loops in G. In particular, we show that this occurs when G is a free non-Abelian group. Also we consider the case when G is a wreath product of ${\mathbb Z}$ with a finite group. To treat this case we prove new estimates for transition probabilities in such wreath products. For any group G generated by a finite set S we define a functor E from category of finite connected graphs to the category of equivalence relations on such graphs. Given a finite connected graph Γ, the value E _G,S (Γ) can be viewed as an asymptotic invariant of G.     

A k-Tree Containing Specified Vertices

A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k > 3. Let G be a graph of order n and let ${S \subseteq V(G)}A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k > 3. Let G be a graph of order n and let S í V(G){S \subseteq V(G)} with κ(S) ≥ 1. Suppose that for every l > κ(S), there exists an integer t such that 1 ￡ t ￡ (k-1)l+2 - ?\fracl-1k ?{1 \le t \leq (k-1)l+2 - \lfloor \frac{l-1}{k} \rfloor} and the degree sum of any t independent vertices of S is at least n + tl − kl − 1. Then G has a k-tree containing S. We also show some new results on a spanning k-tree as corollaries of the above theorem.     

Total domination stable graphs upon edge addition

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. A graph is total domination edge addition stable if the addition of an arbitrary edge has no effect on the total domination number. In this paper, we characterize total domination edge addition stable graphs. We determine a sharp upper bound on the total domination number of total domination edge addition stable graphs, and we determine which combinations of order and total domination number are attainable. We finish this work with an investigation of claw-free total domination edge addition stable graphs.     

Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms

A spanning tree T of a graph G is said to be a treet-spanner if the distance between any two vertices in T is at most t times their distance in G. A graph that has a tree t-spanner is called a treet-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t≥4 and is linearly solvable for t≤2. The case t=3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a−b vertex separators for every pair of non-adjacent vertices a and b are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners. This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed.     

Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids

A matching M is uniquely restricted in a graph G if its saturated vertices induce a subgraph which has a unique perfect matching, namely M itself [M.C. Golumbic, T. Hirst, M. Lewenstein, Uniquely restricted matchings, Algorithmica 31 (2001) 139-154]. G is a König-Egerváry graph provided α(G)+μ(G)=|V(G)| [R.W. Deming, Independence numbers of graphs—an extension of the König-Egerváry theorem, Discrete Math. 27 (1979) 23-33; F. Sterboul, A characterization of the graphs in which the transversal number equals the matching number, J. Combin. Theory Ser. B 27 (1979) 228-229], where μ(G) is the size of a maximum matching and α(G) is the cardinality of a maximum stable set. S is a local maximum stable set of G, and we write S∈Ψ(G), if S is a maximum stable set of the subgraph spanned by S∪N(S), where N(S) is the neighborhood of S. Nemhauser and Trotter [Vertex packings: structural properties and algorithms, Math. Programming 8 (1975) 232-248], proved that any S∈Ψ(G) is a subset of a maximum stable set of G. In [V.E. Levit, E. Mandrescu, Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings, Discrete Appl. Math. 132 (2003) 163-174] we have proved that for a bipartite graph G,Ψ(G) is a greedoid on its vertex set if and only if all its maximum matchings are uniquely restricted. In this paper we demonstrate that if G is a triangle-free graph, then Ψ(G) is a greedoid if and only if all its maximum matchings are uniquely restricted and for any S∈Ψ(G), the subgraph spanned by S∪N(S) is a König-Egerváry graph.     

Safe separators for treewidth

A set of vertices S⊆V is called a safe separator for treewidth, if S is a separator of G, and the treewidth of G equals the maximum of the treewidth over all connected components W of G-S of the graph, obtained by making S a clique in the subgraph of G, induced by W∪S. We show that such safe separators are a very powerful tool for preprocessing graphs when we want to compute their treewidth. We give several sufficient conditions for separators to be safe, allowing such separators, if existing, to be found in polynomial time. In particular, every inclusion minimal separator of size one or two is safe, every minimum separator of size three that does not split off a component with only one vertex is safe, and every inclusion minimal separator that is an almost clique is safe; an almost clique is a set of vertices W such that there is a v∈W with W-{v} a clique. We report on experiments that show significant reductions of instance sizes for graphs from probabilistic networks and frequency assignment.     

Edge covering coloring of nearly bipartite graphs

LetG be a simple graph with vertex setV(G) and edge setE(G). A subsetS ofE(G) is called an edge cover ofG if the subgraph induced byS is a spanning subgraph ofG. The maximum number of edge covers which form a partition ofE(G) is called edge covering chromatic number ofG, denoted by χ′_c(G). It known that for any graphG with minimum degreeδ,δ -1 ≤χ′_c(G) ≤δ. If χ′_c(G) =δ, thenG is called a graph of CI class, otherwiseG is called a graph of CII class. It is easy to prove that the problem of deciding whether a given graph is of CI class or CII class is NP-complete. In this paper, we consider the classification of nearly bipartite graph and give some sufficient conditions for a nearly bipartite graph to be of CI class.     

On matching and total domination in graphs

A set M of edges of a graph G is a matching if no two edges in M are incident to the same vertex. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The matching number is the maximum cardinality of a matching of G, while the total domination number of G is the minimum cardinality of a total dominating set of G. In this paper, we investigate the relationships between the matching and total domination number of a graph. We observe that the total domination number of every claw-free graph with minimum degree at least three is bounded above by its matching number, and we show that every k-regular graph with k?3 has total domination number at most its matching number. In general, we show that no minimum degree is sufficient to guarantee that the matching number and total domination number are comparable.     

On the maximum cardinality search lower bound for treewidth

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The visited degree of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. The maximum visited degree over all MCS-orderings of graph G is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345-353] showed that the treewidth of a graph G is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn) for planar graphs, and give examples of planar graphs G with maximum visited degree k with O(k!) vertices, for all k∈N. Given a graph G, it is NP-complete to determine if its maximum visited degree is at least k, for any fixed k?7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.