Kernels and some operations in edge-coloured digraphs

Let D be an edge-coloured digraph, V(D) will denote the set of vertices of D; a set N⊆V(D) is said to be a kernel by monochromatic paths of D if it satisfies the following two conditions: For every pair of different vertices u,v∈N there is no monochromatic directed path between them and; for every vertex x∈V(D)−N there is a vertex y∈N such that there is an xy-monochromatic directed path.In this paper we consider some operations on edge-coloured digraphs, and some sufficient conditions for the existence or uniqueness of kernels by monochromatic paths of edge-coloured digraphs formed by these operations from another edge-coloured digraphs.     

Kernels in edge-coloured orientations of nearly complete graphs

We call the digraph D an orientation of a graph G if D is obtained from G by the orientation of each edge of G in exactly one of the two possible directions. The digraph D is an m-coloured digraph if the arcs of D are coloured with m-colours.Let D be an m-coloured digraph. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike.A set N⊆V(D) is said to be a kernel by monochromatic paths if it satisfies the two following conditions: (i) for every pair of different vertices u,v∈N there is no monochromatic directed path between them and (ii) for every vertex x∈V(D)-N there is a vertex y∈N such that there is an xy-monochromatic directed path.In this paper we obtain sufficient conditions for an m-coloured orientation of a graph obtained from K_n by deletion of the arcs of K_1,r(0?r?n-1) to have a kernel by monochromatic.     

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.     

Graphs without isometric rays and invariant subgraph properties,I

A ray of a graph G is isometric if every path in R is a shortest path in G. A vertex x of G geodesically dominates a subset A of V(G) if, for every finite S ⊆ V(G − x), there exists an element a of A − {x} such that the interval (set of vertices of all shortest paths) between x and a is disjoint from S. A set A ⊆ V(G) is geodesically closed if it contains all vertices which geodesically dominate A. These geodesically closed sets define a topology, called the geodesic topology, on V(G). We prove that a connected graph G has no isometric rays if and only if the set V(G) endowed with the geodesic topology is compact, or equivalently if and only if the vertex set of every ray in G is geodesically dominated. We prove different invariant subgraph properties for graphs containing no isometric rays. In particular we show that every self-contraction (map which preserves or contracts the edges) of a chordal graph G stabilizes a non-empty finite simplex (complete graph) if and only if G is connected and contains no isometric rays and no infinite simplices. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 99–109, 1998     

Infinite paths in planar graphs III, 1‐way infinite paths

An infinite graph is 2‐indivisible if the deletion of any finite set of vertices from the graph results in exactly one infinite component. Let G be a 4‐connected, 2‐indivisible, infinite, plane graph. It is known that G contains a spanning 1‐way infinite path. In this paper, we prove a stronger result by showing that, for any vertex x and any edge e on a facial cycle of G, there is a spanning 1‐way infinite path in G from x and through e. Results will be used in two forthcoming papers to establish a conjecture of Nash‐Williams. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On the P4-structure of perfect graphs III. Partner decompositions

Vertices x and y in the same graph are called partners if there is a set S of three vertices such that both S ∪ {x} and S ∪ {y} induce a chordless path. If the vertices of G can be distributed into two disjoint classes in such a way that every two partners belong to the same class and that each class induces in G a perfect graph then G is perfect. This theorem generalizes two theorems that were proved before, one by Chvátal and Hoàng, and the other by Hoàng alone.     

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

The strong metric dimension of graphs and digraphs

Let G be a connected (di)graph. A vertex w is said to strongly resolve a pair u,v of vertices of G if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set W of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of W. The smallest cardinality of a strong resolving set for G is called the strong dimension of G. It is shown that the problem of finding the strong dimension of a connected graph can be transformed to the problem of finding the vertex covering number of a graph. Moreover, it is shown that computing this invariant is NP-hard. Related invariants for directed graphs are defined and studied.     

Characterizations of 2-variegated graphs and of 3-variegated graphs

A graph is said to be k-variegated if its vertex set can be partitioned into k equal parts such that each vertex is adjacent to exactly one vertex from every other part not containing it. We prove that a graph G on 2n vertices is 2-variegated if and only if there exists a set S of n independent edges in G such that no cycle in G contains an odd number of edges from S. We also characterize 3-variegated graphs.     

On the Metric Dimension of Infinite Graphs

A set of vertices S resolves a connected graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of a graph G is the minimum cardinality of a resolving set. In this paper we undertake the metric dimension of infinite locally finite graphs, i.e., those infinite graphs such that all its vertices have finite degree. We give some necessary conditions for an infinite graph to have finite metric dimension and characterize infinite trees with finite metric dimension. We also establish some general results about the metric dimension of the Cartesian product of finite and infinite graphs, and obtain the metric dimension of the Cartesian product of several families of graphs.     

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.     

Kernels by monochromatic paths in digraphs with covering number 2

We call the digraph D an k-colored digraph if the arcs of D are colored with k colors. A subdigraph H of D is called monochromatic if all of its arcs are colored alike. A set N⊆V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u,v∈N, there is no monochromatic directed path between them, and (ii) for every vertex x∈(V(D)?N), there is a vertex y∈N such that there is an xy-monochromatic directed path. In this paper, we prove that if D is an k-colored digraph that can be partitioned into two vertex-disjoint transitive tournaments such that every directed cycle of length 3,4 or 5 is monochromatic, then D has a kernel by monochromatic paths. This result gives a positive answer (for this family of digraphs) of the following question, which has motivated many results in monochromatic kernel theory: Is there a natural numberlsuch that if a digraphDisk-colored so that every directed cycle of length at mostlis monochromatic, thenDhas a kernel by monochromatic paths?     

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.     

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.     

On the Independent Domination Number of Regular Graphs

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. In this paper, we consider questions about independent domination in regular graphs.     

Independent domination in chordal graphs

A graph chordal if it does not contain any cycle of length greater than three as an induced subgraph. A set of S of vertices of a graph G = (V,E) is independent if not two vertices in S are adjacent, and is dominating if every vertex in V?S is adjacent to some vertex in S. We present a linear algorithm to locate a minimum weight independent dominating set in a chordal graph with 0–1 vertex weights.     

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.     

Locating and total dominating sets in trees

A set S of vertices in a graph G=(V,E) is a total dominating set of G if every vertex of V is adjacent to a vertex in S. We consider total dominating sets of minimum cardinality which have the additional property that distinct vertices of V are totally dominated by distinct subsets of the total dominating set.     

A survey of selected recent results on total domination in graphs

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. In this paper, we offer a survey of selected recent results on total domination in graphs.     

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.