On the oriented chromatic number of grids

In this paper, we focus on the oriented coloring of graphs. Oriented coloring is a coloring of the vertices of an oriented graph G without symmetric arcs such that (i) no two neighbors in G are assigned the same color, and (ii) if two vertices u and v such that (u,v)∈A(G) are assigned colors c(u) and c(v), then for any (z,t)∈A(G), we cannot have simultaneously c(z)=c(v) and c(t)=c(u). The oriented chromatic number of an unoriented graph G is the smallest number k of colors for which any of the orientations of G can be colored with k colors.The main results we obtain in this paper are bounds on the oriented chromatic number of particular families of planar graphs, namely 2-dimensional grids, fat trees and fat fat trees.     

Note on the connectivity of line graphs

Let G be a connected graph with vertex set V(G), edge set E(G), vertex-connectivity κ(G) and edge-connectivity λ(G).A subset S of E(G) is called a restricted edge-cut if G−S is disconnected and each component contains at least two vertices. The restricted edge-connectivity λ₂(G) is the minimum cardinality over all restricted edge-cuts. Clearly λ₂(G)?λ(G)?κ(G).In 1969, Chartrand and Stewart have shown that

     

Feedback vertex sets in star graphs

In a graph G=(V,E), a subset F⊂V(G) is a feedback vertex set of G if the subgraph induced by V(G)?F is acyclic. In this paper, we propose an algorithm for finding a small feedback vertex set of a star graph. Indeed, our algorithm can derive an upper bound to the size of the feedback vertex set for star graphs. Also by applying the properties of regular graphs, a lower bound can easily be achieved for star graphs.     

Consensus models: Computational complexity aspects in modern approaches to the list coloring problem

In the paper we study new approaches to the problem of list coloring of graphs. In the problem we are given a simple graph G=(V,E) and, for every v∈V, a nonempty set of integers S(v); we ask if there is a coloring c of G such that c(v)∈S(v) for every v∈V. Modern approaches, connected with applications, change the question—we now ask if S can be changed, using only some elementary transformations, to ensure that there is such a coloring and, if the answer is yes, what is the minimal number of changes. In the paper for studying the adding, the trading and the exchange models of list coloring, we use the following transformations:

•

adding of colors (the adding model): select two vertices u, v and a color c∈S(u); add c to S(v), i.e. set S(v):=S(v)∪{c};

•

trading of colors (the trading model): select two vertices u, v and a color c∈S(u); move c from S(u) to S(v), i.e. set S(u):=S(u)?{c} and S(v):=S(v)∪{c};

•

exchange of colors (the exchange model): select two vertices u, v and two colors c∈S(u), d∈S(v); exchange c with d, i.e. set S(u):=(S(u)?{c})∪{d} and S(v):=(S(v)?{d})∪{c}.

Our study focuses on computational complexity of the above models and their edge versions. We consider these problems on complete graphs, graphs with bounded cyclicity and partial k-trees, receiving in all cases polynomial algorithms or proofs of NP-hardness.     

Restricted arc-connectivity of digraphs

Since interconnection networks are often modeled by graphs or digraphs, the edge-connectivity of a graph or arc-connectivity of a digraph are important measurements for fault tolerance of networks.The restricted edge-connectivity λ^′(G) of a graph G is the minimum cardinality over all edge-cuts S in a graph G such that there are no isolated vertices in G−S. A connected graph G is called λ^′-connected, if λ^′(G) exists.In 1988, Esfahanian and Hakimi [A.H. Esfahanian, S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988), 195-199] have shown that each connected graph G of order n?4, except a star, is λ^′-connected and satisfies λ^′(G)?ξ(G), where ξ(G) is the minimum edge-degree of G.If D is a strongly connected digraph, then we call in this paper an arc set S a restricted arc-cut of D if D−S has a non-trivial strong component D₁ such that D−V(D₁) contains an arc. The restricted arc-connectivity λ^′(D) is the minimum cardinality over all restricted arc-cuts S.We observe that the recognition problem, whether λ^′(D) exists for a strongly connected digraph D is solvable in polynomial time. Furthermore, we present some analogous results to the above mentioned theorem of Esfahanian and Hakimi for digraphs, and we show that this theorem follows easily from one of our results.     

On Reversible Cascades in Scale-Free and Erdős-Rényi Random Graphs

Consider the following cascading process on a simple undirected graph G(V,E) with diameter Δ. In round zero, a set S?V of vertices, called the seeds, are active. In round i+1, i∈?, a non-isolated vertex is activated if at least a ρ∈(0,1] fraction of its neighbors are active in round i; it is deactivated otherwise. For k∈?, let min-seed^(k)(G,ρ) be the minimum number of seeds needed to activate all vertices in or before round k. This paper derives upper bounds on min-seed^(k)(G,ρ). In particular, if G is connected and there exist constants C>0 and γ>2 such that the fraction of degree-k vertices in G is at most C/k ^γ for all k∈?⁺, then min-seed^(Δ)(G,ρ)=O(?ρ ^γ?1|V|?). Furthermore, for n∈?⁺, p=Ω((ln(e/ρ))/(ρn)) and with probability 1?exp(?n ^Ω(1)) over the Erd?s-Rényi random graphs G(n,p), min-seed⁽¹⁾(G(n,p),ρ)=O(ρn).     

The complexity of determining the rainbow vertex-connection of a graph

A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors, which was introduced by Krivelevich and Yuster. 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 G rainbow vertex-connected. In this paper, we study the complexity of determining the rainbow vertex-connection of a graph and prove that computing rvc(G) is NP-Hard. Moreover, we show that it is already NP-Complete to decide whether rvc(G)=2. We also prove that the following problem is NP-Complete: given a vertex-colored graph G, check whether the given coloring makes G rainbow vertex-connected.     

A new sufficient condition for Hamiltonicity of graphs

Rahman and Kaykobad proved the following theorem on Hamiltonian paths in graphs. Let G be a connected graph with n vertices. If d(u)+d(v)+δ(u,v)?n+1 for each pair of distinct non-adjacent vertices u and v in G, where δ(u,v) is the length of a shortest path between u and v in G, then G has a Hamiltonian path. It is shown that except for two families of graphs a graph is Hamiltonian if it satisfies the condition in Rahman and Kaykobad's theorem. The result obtained in this note is also an answer for a question posed by Rahman and Kaykobad.     

Fault-diameter of Cartesian graph bundles

Cartesian graph bundles is a class of graphs that is a generalization of the Cartesian graph products. Let G be a kG-connected graph and Dc(G) denote the diameter of G after deleting any of its c<kG vertices. We prove that Da+b+1(G)?Da(F)+Db(B)+1 if G is a graph bundle with fibre F over base B, a<kF, and b<kB.     

The Hub Number of Sierpiński-Like Graphs

A set Q⊆V is a hub set of a graph G=(V,E) if, for every pair of vertices u,v∈V∖Q, there exists a path from u to v such that all intermediate vertices are in Q. The hub number of G is the minimum size of a hub set in G. This paper derives the hub numbers of Sierpiński-like graphs including: Sierpiński graphs, extended Sierpiński graphs, and Sierpiński gasket graphs. Meanwhile, the corresponding minimum hub sets are also obtained.     

The (strong) rainbow connection numbers of Cayley graphs on Abelian groups

A path in an edge-colored graph G, whose adjacent edges may have the same color, is called a rainbow path if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the minimum integer i for which there exists an i-edge-coloring of G such that every two distinct vertices of G are connected by a rainbow path. The strong rainbow connection number src(G) of G is the minimum integer i for which there exists an i-edge-coloring of G such that every two distinct vertices u and v of G are connected by a rainbow path of length d(u,v). In this paper, we give upper and lower bounds of the (strong) rainbow connection numbers of Cayley graphs on Abelian groups. Moreover, we determine the (strong) rainbow connection numbers of some special cases.     

A note on the Hadwiger number of circular arc graphs

The intention of this note is to motivate the researchers to study Hadwiger's conjecture for circular arc graphs. Let η(G) denote the largest clique minor of a graph G, and let χ(G) denote its chromatic number. Hadwiger's conjecture states that η(G)?χ(G) and is one of the most important and difficult open problems in graph theory. From the point of view of researchers who are sceptical of the validity of the conjecture, it is interesting to study the conjecture for graph classes where η(G) is guaranteed not to grow too fast with respect to χ(G), since such classes of graphs are indeed a reasonable place to look for possible counterexamples. We show that in any circular arc graph G, η(G)?2χ(G)−1, and there is a family with equality. So, it makes sense to study Hadwiger's conjecture for this family.     

Radio number of ladder graphs

Let G be a connected graph with diameter diam(G). The radio number for G, denoted by rn(G), is the smallest integer k such that there exists a function f: V(G)→{0, 1, 2, …, k} with the following satisfied for all vertices u and v:|f(u)?f(v)|≥diam (G)?d _G (u, v)+1, where d _G (u, v) is the distance between u and v in G. In this paper, we determine the radio number of ladder graphs.     

On the stability number of the edge intersection of two graphs

Let G be the graph obtained as the edge intersection of two graphs G₁, G₂ on the same vertex set V. We show that if at least one of G₁, G₂ is perfect, then α(G)?α(G₁)·α(G₂), where α() is the cardinality of the largest stable set. Moreover, for general G₁ and G₂, we show that α(G)?R(α(G₁)+1,α(G₂)+1)−1, where R(k,?) is the Ramsey number.     

Vertex fault tolerance of optimal-κ graphs and super-κ graphs

A connected graph G is optimal-κ if κ(G)=δ(G). It is super-κ if every minimum vertex cut isolates a vertex. An optimal-κ graph G is m-optimal-κ if for any vertex set S⊆V(G) with |S|?m, G−S is still optimal-κ. We define the vertex fault tolerance with respect to optimal-κ, denoted by Oκ(G), as the maximum integer m such that G is m-optimal-κ. The concept of vertex fault tolerance with respect to super-κ, denoted by Sκ(G), is defined in a similar way. In this paper, we show that min{κ₁(G)−δ(G),δ(G)−1}?Oκ(G)?δ(G)−1 and min{κ₁(G)−δ(G)−1,δ(G)−1}?Sκ(G)?δ(G)−1, where κ₁(G) is the 1-extra connectivity of G. Furthermore, when the graph is triangle free, more refined lower bound can be derived for Oκ(G).     

Ranking numbers of graphs

Given a graph G, a vertex ranking (or simply, ranking) of G is a mapping f from V(G) to the set of all positive integers, such that for any path between two distinct vertices u and v with f(u)=f(v), there is a vertex w in the path with f(w)>f(u). If f is a ranking of G, the ranking number of G under f, denoted γf(G), is defined by , and the ranking number of G, denoted γ(G), is defined by . The vertex ranking problem is to determine the ranking number γ(G) of a given graph G. This problem is a natural model for the manufacturing scheduling problem. We study the ranking numbers of graphs in this paper. We consider the relation between the ranking numbers and the minimal cut sets, and the relation between the ranking numbers and the independent sets. From this, we obtain the ranking numbers of the powers of paths and the powers of cycles, the Cartesian product of P₂ with Pn or Cn, and the caterpilars. And we also find the vertex ranking numbers of the composition of two graphs in this paper.     

Lucky labelings of graphs

Suppose the vertices of a graph G were labeled arbitrarily by positive integers, and let S(v) denote the sum of labels over all neighbors of vertex v. A labeling is lucky if the function S is a proper coloring of G, that is, if we have S(u)≠S(v) whenever u and v are adjacent. The least integer k for which a graph G has a lucky labeling from the set {1,2,…,k} is the lucky number of G, denoted by η(G).Using algebraic methods we prove that η(G)?k+1 for every bipartite graph G whose edges can be oriented so that the maximum out-degree of a vertex is at most k. In particular, we get that η(T)?2 for every tree T, and η(G)?3 for every bipartite planar graph G. By another technique we get a bound for the lucky number in terms of the acyclic chromatic number. This gives in particular that for every planar graph G. Nevertheless we offer a provocative conjecture that η(G)?χ(G) for every graph G.     

Super restricted edge connected Cartesian product graphs

An edge-cut F of a connected graph G is called a restricted edge-cut if G−F contains no isolated vertices. The minimum cardinality of all restricted edge-cuts is called the restricted edge-connectivity λ^′(G) of G. A graph G is said to be λ^′-optimal if λ^′(G)=ξ(G), where ξ(G) is the minimum edge-degree of G. A graph is said to be super-λ^′ if every minimum restricted edge-cut isolates an edge. This article gives a sufficient condition for Cartesian product graphs to be super-λ^′. Using this result, certain classes of networks which are recursively defined by the Cartesian product can be simply shown to be super-λ^′.     

On an infinite family of graphs with information ratio 2 − 1/k

In this paper we consider the secret sharing problem on special access structures with minimal qualified subsets of size two, i.e. secret sharing on graphs. This means that the participants are the vertices of the graph and the qualified subsets are the subsets of V(G) spanning at least one edge. The information ratio of a graph G is denoted by R(G) and is defined as the ratio of the greatest size of the shares a vertex has to remember and of the size of the secret. Since the determination of the exact information ratio is a non-trivial problem even for small graphs (i.e. for V(G) = 6), every construction can be of particular interest. Let k be the maximal degree in G. In this paper we prove that R(G) = 2 ? 1/k for every graph G with the following properties: (A) every vertex has at most one neighbour of degree one; (B) vertices of degree at least 3 are not connected by an edge; (C) the girth of the graph is at least 6. We prove this by using polyhedral combinatorics arguments and the entropy method.     

Finding a dominating set on bipartite graphs

Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O^∗(²n−z), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O^∗(²n/2). Another implication is an algorithm for general graphs whose running time is O(n^1.7088).