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.     

Properties of connected graphs having minimum degree distance

The degree distance of a connected graph, introduced by Dobrynin, Kochetova and Gutman, has been studied in mathematical chemistry. In this paper some properties of graphs having minimum degree distance in the class of connected graphs of order n and size m≥n−1 are deduced. It is shown that any such graph G has no induced subgraph isomorphic to P₄, contains a vertex z of degree n−1 such that G−z has at most one connected component C such that |C|≥2 and C has properties similar to those of G.For any fixed k such that k=0,1 or k≥3, if m=n+k and n≥k+3 then the extremal graph is unique and it is isomorphic to K₁+(K_1,k+1∪(n−k−3)K₁).     

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

Maximum information stored in a labeled connected network with minimum edges

Given a set X, we consider the problem of finding a graph G with vertex set X and the minimum number of edges such that for i = 1, . . . , m, the subgraph G _i induced from pattern i is a label connected graph with minimum edges. In the paper, we show that the problem is NP hard and develop a heuristic algorithm to get a fewer number of edges to store patterns.     

A linear algorithm for the domination number of a series-parallel graph

A vertex u in an undirected graph G = (V, E) is said to dominate all its adjacent vertices and itself. A subset D of V is a dominating set in G if every vertex in G is dominated by a vertex in D, and is a minimum dominating set in G if no other dominating set in G has fewer vertices than D. The domination number of G is the cardinality of a minimum dominating set in G.The problem of determining, for a given positive integer k and an undirected graph G, whether G has a dominating set D in G satisfying ¦D¦ ≤ k, is a well-known NP-complete problem. Cockayne have presented a linear time algorithm for finding a minimum dominating set in a tree. In this paper, we will present a linear time algorithm for finding a minimum dominating set in a series-parallel graph.     

A lower bound for the convexity number of some graphs

Given a connected graphG, we say that a setC ?V(G) is convex inG if, for every pair of verticesx, y ∈ C, the vertex set of everyx-y geodesic inG is contained inC. The convexity number ofG is the cardinality of a maximal proper convex set inG. In this paper, we show that every pairk, n of integers with 2 ≤k ≤ n?1 is realizable as the convexity number and order, respectively, of some connected triangle-free graph, and give a lower bound for the convexity number ofk-regular graphs of ordern withn>k+1.     

Neighbor Sum Distinguishing Index

We consider proper edge colorings of a graph G using colors of the set {1, . . . , k}. Such a coloring is called neighbor sum distinguishing if for any pair of adjacent vertices x and y the sum of colors taken on the edges incident to x is different from the sum of colors taken on the edges incident to y. The smallest value of k in such a coloring of G is denoted by ndi_Σ(G). In the paper we conjecture that for any connected graph G ≠ C ₅ of order n ≥ 3 we have ndi_Σ(G) ≤ Δ(G) + 2. We prove this conjecture for several classes of graphs. We also show that ndi_Σ(G) ≤ 7Δ(G)/2 for any graph G with Δ(G) ≥ 2 and ndi_Σ(G) ≤ 8 if G is cubic.     

Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph

Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n ? 2. These conditions are best possible. A related conjecture also is proposed.     

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.     

Minimum 2-tuple dominating set of permutation graphs

For a fixed positive integer k, a k-tuple dominating set of a graph G=(V,E) is a subset D?V such that every vertex in V is dominated by at least k vertex in D. The k-tuple domination number γ _×k (G) is the minimum size of a k-tuple dominating set of G. The special case when k=1 is the usual domination. The case when k=2 was called double domination or 2-tuple domination. A 2-tuple dominating set D ₂ is said to be minimal if there does not exist any D′?D ₂ such that D′ is a 2-tuple dominating set of G. A 2-tuple dominating set D ₂, denoted by γ _×2(G), is said to be minimum, if it is minimal as well as it gives 2-tuple domination number. In this paper, we present an efficient algorithm to find a minimum 2-tuple dominating set on permutation graphs with n vertices which runs in O(n ²) time.     

An Implicit Degree Condition for Pancyclicity of Graphs

Zhu, Li and Deng introduced in 1989 the definition of implicit degree of a vertex v in a graph G, denoted by id(v), by using the degrees of the vertices in its neighborhood and the second neighborhood. And they obtained sufficient conditions with implicit degrees for a graph to be hamiltonian. In this paper, we prove that if G is a 2–connected graph of order n ≥ 3 such that id(v) ≥ n/2 for each vertex v of G, then G is pancyclic unless G is bipartite, or else n = 4r, r ≥ 2 and G is in a class of graphs F _4r defined in the paper.     

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.     

Tank-Ring Factors in Supereulerian Claw-Free Graphs

A graph G has a tank-ring factor F if F is a connected spanning subgraph with all vertices of degree 2 or 4 that consists of one cycle C and disjoint triangles attaching to exactly one vertex of C such that every component of G ? C contains exactly two vertices. In this paper, we show the following results. (1) Every supereulerian claw-free graph G with 1-hourglass property contains a tank-ring factor. (2) Every supereulerian claw-free graph with 2-hourglass property is Hamiltonian.     

<Emphasis Type="Italic">s</Emphasis>-Vertex Pancyclic Index

A graph G is vertex pancyclic if for each vertex \({v \in V(G)}\) , and for each integer k with 3 ≤ k ≤ |V(G)|, G has a k-cycle C _k such that \({v \in V(C_k)}\) . Let s ≥ 0 be an integer. If the removal of at most s vertices in G results in a vertex pancyclic graph, we say G is an s-vertex pancyclic graph. Let G be a simple connected graph that is not a path, cycle or K _1,3. Let l(G) = max{m : G has a divalent path of length m that is not both of length 2 and in a K ₃}, where a divalent path in G is a path whose interval vertices have degree two in G. The s-vertex pancyclic index of G, written vp _s (G), is the least nonnegative integer m such that L ^m (G) is s-vertex pancyclic. We show that for a given integer s ≥ 0,

$vp_s(G)\le \left\{\begin{array}{l@{\quad}l}\qquad\quad\quad\,\,\,\,\,\,\, l(G)+s+1: \quad {\rm if} \,\, 0 \le s \le 4 \\ l(G)+\lceil {\rm log}_2(s-2) \rceil+4: \quad {\rm if} \,\, s \ge 5 \end{array}\right.$

And we improve the bound for essentially 3-edge-connected graphs. The lower bound and whether the upper bound is sharp are also discussed.

     

Spanning Connectivity of the Power of a Graph and Hamilton-Connected Index of a Graph

Let G = (V, E) be a connected graph. The hamiltonian index h(G) (Hamilton-connected index hc(G)) of G is the least nonnegative integer k for which the iterated line graph L ^k (G) is hamiltonian (Hamilton-connected). In this paper we show the following. (a) If |V(G)| ≥ k + 1 ≥ 4, then in G ^k , for any pair of distinct vertices {u, v}, there exists k internally disjoint (u, v)-paths that contains all vertices of G; (b) for a tree T,  h(T) ≤ hc(T) ≤ h(T) + 1, and for a unicyclic graph G,  h(G) ≤ hc(G) ≤ max{h(G) + 1, k′ + 1}, where k′ is the length of a longest path with all vertices on the cycle such that the two ends of it are of degree at least 3 and all internal vertices are of degree 2; (c) we also characterize the trees and unicyclic graphs G for which hc(G) = h(G) + 1.     

Connectivity keeping paths in k‐connected graphs

A result of G. Chartrand, A. Kaugars, and D. R. Lick [Proc Amer Math Soc 32 (1972), 63–68] says that every finite, k‐connected graph G of minimum degree at least ?3k/2? contains a vertex x such that G?x is still k‐connected. We generalize this result by proving that every finite, k‐connected graph G of minimum degree at least ?3k/2?+m?1 for a positive integer m contains a path P of length m?1 such that G?V(P) is still k‐connected. This has been conjectured in a weaker form by S. Fujita and K. Kawarabayashi [J Combin Theory Ser B 98 (2008), 805–811]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 61–69, 2010.     

An Ore-Type Theorem on Hamiltonian Square Cycles

The kth power of a cycle C is the graph obtained from C by joining every pair of vertices with distance at most k on C. The second power of a cycle is called a square cycle. Pósa conjectured that every graph with minimum degree at least 2n/3 contains a hamiltonian square cycle. Later, Seymour proposed a more general conjecture that if G is a graph with minimum degree at least (kn)/(k + 1), then G contains the kth power of a hamiltonian cycle. Here we prove an Ore-type version of Pósa’s conjecture that if G is a graph in which deg(u) + deg(v) ≥ 4n/3 ? 1/3 for all non-adjacent vertices u and v, then for sufficiently large n, G contains a hamiltonian square cycle unless its minimum degree is exactly n/3 + 2 or n/3 + 5/3. A consequence of this result is an Ore-type analogue of a theorem of Aigner and Brandt.     

The k-Dominating Graph

Given a graph G, the k-dominating graph of G, D _k (G), is defined to be the graph whose vertices correspond to the dominating sets of G that have cardinality at most k. Two vertices in D _k (G) are adjacent if and only if the corresponding dominating sets of G differ by either adding or deleting a single vertex. The graph D _k (G) aids in studying the reconfiguration problem for dominating sets. In particular, one dominating set can be reconfigured to another by a sequence of single vertex additions and deletions, such that the intermediate set of vertices at each step is a dominating set if and only if they are in the same connected component of D _k (G). In this paper we give conditions that ensure D _k (G) is connected.     

The game of arboricity

Using a fixed set of colors C, Ann and Ben color the edges of a graph G so that no monochromatic cycle may appear. Ann wins if all edges of G have been colored, while Ben wins if completing a coloring is not possible. The minimum size of C for which Ann has a winning strategy is called the game arboricity of G, denoted by A_g(G). We prove that A_g(G)?3k for any graph G of arboricity k, and that there are graphs such that A_g(G)?2k-2. The upper bound is achieved by a suitable version of the activation strategy, used earlier for the vertex coloring game. We also provide two other strategies based on induction and acyclic colorings.     

Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width

Let M=(V,E,A) be a mixed graph with vertex set V, edge set E and arc set A. A cycle cover of M is a family C={C₁,…,C_k} of cycles of M such that each edge/arc of M belongs to at least one cycle in C. The weight of C is . The minimum cycle cover problem is the following: given a strongly connected mixed graph M without bridges, find a cycle cover of M with weight as small as possible. The Chinese postman problem is: given a strongly connected mixed graph M, find a minimum length closed walk using all edges and arcs of M. These problems are NP-hard. We show that they can be solved in polynomial time if M has bounded tree-width.