Acyclic graphoidal covers and path partitions in a graph

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. A path partition of a graph G is a collection P of paths in G such that every edge of G is in exactly one path in P. The minimum cardinality of a path partition of G is called thepath partition number of G and is denoted by π. In this paper we determine η_a and π for several classes of graphs and obtain a characterization of all graphs with Δ 4 and η_a = Δ − 1. We also obtain a characterization of all graphs for which η_a = π.     

The edge chromatic number of a directed/mixed multigraph

We consider colorings of the directed and undirected edges of a mixed multigraph G by an ordered set of colors. We color each undirected edge in one color and each directed edge in two colors, such that the color of the first half of a directed edge is smaller than the color of the second half. The colors used at the same vertex are all different. A bound for the minimum number of colors needed for such colorings is obtained. In the case where G has only directed edges, we provide a polynomal algorithm for coloring G with a minimum number of colors. An unsolved problem is formulated. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 267–273, 1999     

Sufficient conditions for graphs to be λ′‐optimal,super‐edge‐connected,and maximally edge‐connected

The restricted‐edge‐connectivity of a graph G, denoted by λ′(G), is defined as the minimum cardinality over all edge‐cuts S of G, where G‐S contains no isolated vertices. The graph G is called λ′‐optimal, if λ′(G) = ξ(G), where ξ(G) is the minimum edge‐degree in G. A graph is super‐edge‐connected, if every minimum edge‐cut consists of edges adjacent to a vertex of minimum degree. In this paper, we present sufficient conditions for arbitrary, triangle‐free, and bipartite graphs to be λ′‐optimal, as well as conditions depending on the clique number. These conditions imply super‐edge‐connectivity, if δ (G) ≥ 3, and the equality of edge‐connectivity and minimum degree. Different examples will show that these conditions are best possible and independent of other results in this area. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 228–246, 2005     

On the adjacent vertex-distinguishing acyclic edge coloring of some graphs

A proper edge coloring of a graph G is called adjacent vertex-distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the coloring set of edges incident with u is not equal to the coloring set of edges incident with v, where uv ∈ E(G). The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by x′ _Aa (G), is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. If a graph G has an adjacent vertex distinguishing acyclic edge coloring, then G is called adjacent vertex distinguishing acyclic. In this paper, we obtain adjacent vertex-distinguishing acyclic edge coloring of some graphs and put forward some conjectures.     

Paired-Domination Subdivision Numbers of Graphs

A paired-dominating set of a graph G = (V, E) with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γ _pr (G), is the minimum cardinality of a paired-dominating set of G. The paired-domination subdivision number sd _γpr (G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the paired-domination number. In this paper we establish upper bounds on the paired-domination subdivision number and pose some problems and conjectures.     

Oriented walk double covering and bidirectional double tracing

An oriented walk double covering of a graph G is a set of oriented closed walks, that, traversed successively, combined will have traced each edge of G once in each direction. A bidirectional double tracing of a graph G is an oriented walk double covering that consists of a single closed walk. A retracting in a closed walk is the immediate succession of an edge by its inverse. Every graph with minimum degree 2 has a retracting free oriented walk double covering and every connected graph has a bidirectional double tracing. The minimum number of closed walks in a retracting free oriented walk double covering of G is denoted by c(G). The minimum number of retractings in a bidirectional double tracing of G is denoted by r(G). We shall prove that for all connected noncycle graphs G with minimum degree at least 2, r(G) = c(G) − 1. The problem of characterizing those graphs G for which r(G) = 0 was raised by Ore. Thomassen solved this problem by relating it to the existence of certain spanning trees. We generalize this result, and relate the parameters r(G), c(G) to spanning trees of G. This relation yields a polynomial time algorithm to determine the parameters c(G) and r(G). © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 89–102, 1998     

Game chromatic index of k‐degenerate graphs

We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and assign it a color different from the colors of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k − 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001     

An Upper Bound for the Total Domination Subdivision Number of a Graph

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_gt(G){{\rm sd}_{\gamma_t}(G)} is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper, we prove that sd_gt(G) ￡ 2g_t(G)-1{{\rm sd}_{\gamma_t}(G)\leq 2\gamma_t(G)-1} for every simple connected graph G of order n ≥ 3.     

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.     

The edge reconstruction number of a disconnected graph

The edge reconstruction number of a graph G, RN(G), is the minimum number of edge deleted subgraphs required to determine G up to isomorphism. We prove the following results for a disconnected graph G with at least two nontrivial components. If G has a pair of nontrivial nonisomorphic components then RN(G) ≤ 3. If G has a pair of nontrivial nonisomorphic components, is not a forest, and contains a nontrivial component other than K₃ or K_1,3 then RN(G) ≤ 2. Finally, if all nontrivial components of G are isomorphic to a graph with k edges, then RN(G) ≤ k + 2. The edge reconstruction results in this paper are similar to the vertex reconstruction results stated by Myrvold (“The Ally-Reconstruction Number of a Disconnected Graph,” Ars Combinatoria, Vol. 28 [1989] pp. 123-127), but a significant difference is that the edge reconstruction number of a disconnected graph is often two, while the vertex reconstruction number of a graph is always three or more. © 1995 John Wiley & Sons, Inc.     

The rainbow connection of a graph is (at most) reciprocal to its minimum degree

An edge‐colored graph Gis rainbow edge‐connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make Grainbow edge‐connected. We prove that if Ghas nvertices and minimum degree δ then rc(G)<20n/δ. This solves open problems from Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster (Electron J Combin 15 (2008), #R57) and S. Chakrborty, E. Fischer, A. Matsliah, and R. Yuster (Hardness and algorithms for rainbow connectivity, Freiburg (2009), pp. 243–254). A vertex‐colored graph Gis rainbow vertex‐connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex‐connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make Grainbow vertex‐connected. One cannot upper‐bound one of these parameters in terms of the other. Nevertheless, we prove that if Ghas nvertices and minimum degree δ then rvc(G)<11n/δ. We note that the proof in this case is different from the proof for the edge‐colored case, and we cannot deduce one from the other. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 185–191, 2010     

Looseness of Plane Graphs

A face of a vertex coloured plane graph is called loose if the number of colours used on its vertices is at least three. The looseness of a plane graph G is the minimum k such that any surjective k-colouring involves a loose face. In this paper we prove that the looseness of a connected plane graph G equals the maximum number of vertex disjoint cycles in the dual graph G* increased by 2. We also show upper bounds on the looseness of graphs based on the number of vertices, the edge connectivity, and the girth of the dual graphs. These bounds improve the result of Negami for the looseness of plane triangulations. We also present infinite classes of graphs where the equalities are attained.     

Vertex‐distinguishing edge colorings of random graphs

A proper edge coloring of a simple graph G is called vertex‐distinguishing if no two distinct vertices are incident to the same set of colors. We prove that the minimum number of colors required for a vertex‐distinguishing coloring of a random graph of order n is almost always equal to the maximum degree Δ(G) of the graph. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 89–97, 2002     

A polynomial algorithm for finding (<Emphasis Type="Italic">g,f</Emphasis>)-colorings orthogonal to stars in bipartite graphs

Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two nonnegative integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). A (g, f)-coloring of G is a generalized edge-coloring in which each color appears at each vertex x at least g(x) and at most f(x) times. In this paper a polynomial algorithm to find a (g, f)-coloring of a bipartite graph with some constraints using the minimum number of colors is given. Furthermore, we show that the results in this paper are best possible.     

List Coloring of Random and Pseudo-Random Graphs

choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from S(v). It is shown that the choice number of the random graph G(n, p(n)) is almost surely whenever . A related result for pseudo-random graphs is proved as well. By a special case of this result, the choice number (as well as the chromatic number) of any graph on n vertices with minimum degree at least in which no two distinct vertices have more than common neighbors is at most . Received: October 13, 1997     

Claw‐free graphs and 2‐factors that separate independent vertices

In this article, we prove that a line graph with minimum degree δ≥7 has a spanning subgraph in which every component is a clique of order at least three. This implies that if G is a line graph with δ≥7, then for any independent set S there is a 2‐factor of G such that each cycle contains at most one vertex of S. This supports the conjecture that δ≥5 is sufficient to imply the existence of such a 2‐factor in the larger class of claw‐free graphs. It is also shown that if G is a claw‐free graph of order n and independence number α with δ≥2n/α?2 and n≥3α³/2, then for any maximum independent set S, G has a 2‐factor with α cycles such that each cycle contains one vertex of S. This is in support of a conjecture that δ≥n/α≥5 is sufficient to imply the existence of a 2‐factor with α cycles, each containing one vertex of a maximum independent set. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 251–263, 2012     

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.     

Upper bounds on vertex distinguishing chromatic index of some Halin graphs

A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph G is denoted by ???? _s (G). In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with ??(G) ?? 4, respectively.     

Interval coloring of (3,4)‐biregular bipartite graphs having large cubic subgraphs

An interval coloring of a graph is a proper edge coloring such that the set of used colors at every vertex is an interval of integers. Generally, it is an NP‐hard problem to decide whether a graph has an interval coloring or not. A bipartite graph G = (A,B;E) is (α, β)‐biregular if each vertex in A has degree α and each vertex in B has degree β. In this paper we prove that if the (3,4)‐biregular graph G has a cubic subgraph covering the set B then G has an interval coloring. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 122–128, 2004     

A Complete Solution to Spectrum Problem for Five‐Vertex Graphs with Application to Traffic Grooming in Optical Networks

A G‐design of order n is a decomposition of the complete graph on n vertices into edge‐disjoint subgraphs isomorphic to G. Grooming uniform all‐to‐all traffic in optical ring networks with grooming ratio C requires the determination of graph decompositions of the complete graph on n vertices into subgraphs each having at most C edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The existence spectrum problem of G‐designs for five‐vertex graphs is a long standing problem posed by Bermond, Huang, Rosa and Sotteau in 1980, which is closely related to traffic groomings in optical networks. Although considerable progress has been made over the past 30 years, the existence problems for such G‐designs and their related traffic groomings in optical networks are far from complete. In this paper, we first give a complete solution to this spectrum problem for five‐vertex graphs by eliminating all the undetermined possible exceptions. Then, we determine almost completely the minimum drop cost of 8‐groomings for all orders n by reducing the 37 possible exceptions to 8. Finally, we show the minimum possible drop cost of 9‐groomings for all orders n is realizable with 14 exceptions and 12 possible exceptions.