The vertex linear arboricity of distance graphs

A distance graph is a graph G(R,D) with the set of all points of the real line as vertex set and two vertices u,v∈R are adjacent if and only if |u-v|∈D where the distance set D is a subset of the positive real numbers. Here, the vertex linear arboricity of G(R,D) is determined when D is an interval between 1 and δ. In particular, the vertex linear arboricity of integer distance graphs G(D) is discussed, too.     

On distance two graphs of upper bound graphs

For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,E_U), where uv∈E_U if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS₂(G) is the graph with vertex set V(DS₂(G))=V(G) and u,v∈V(DS₂(G)) are adjacent if and only if d_G(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs.     

On the eccentric distance sum of trees and unicyclic graphs

Let G be a simple connected graph with the vertex set V(G). The eccentric distance sum of G is defined as ξd(G)=_∑v∈V(G)ε(v)DG(v), where ε(v) is the eccentricity of the vertex v and DG(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. In this paper we characterize the extremal unicyclic graphs among n-vertex unicyclic graphs with given girth having the minimal and second minimal eccentric distance sum. In addition, we characterize the extremal trees with given diameter and minimal eccentric distance sum.     

The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism of D to H if uv∈A(D) implies f(u)f(v)∈A(H). For a fixed digraph H, the homomorphism problem is to decide whether an input digraph D admits a homomorphism to H or not, and is denoted as HOM(H).An optimization version of the homomorphism problem was motivated by a real-world problem in defence logistics and was introduced in Gutin, Rafiey, Yeo and Tso (2006) [13]. If each vertex u∈V(D) is associated with costs c_i(u),i∈V(H), then the cost of the homomorphism f is ∑_u∈V(D)c_f(u)(u). For each fixed digraph H, we have the minimum cost homomorphism problem forH and denote it as MinHOM(H). The problem is to decide, for an input graph D with costs c_i(u),u∈V(D),i∈V(H), whether there exists a homomorphism of D to H and, if one exists, to find one of minimum cost.Although a complete dichotomy classification of the complexity of MinHOM(H) for a digraph H remains an unsolved problem, complete dichotomy classifications for MinHOM(H) were proved when H is a semicomplete digraph Gutin, Rafiey and Yeo (2006) [10], and a semicomplete multipartite digraph Gutin, Rafiey and Yeo (2008) [12] and [11]. In these studies, it is assumed that the digraph H is loopless. In this paper, we present a full dichotomy classification for semicomplete digraphs with possible loops, which solves a problem in Gutin and Kim (2008) [9].     

On the structure of strong 3-quasi-transitive digraphs

In this paper, D=(V(D),A(D)) denotes a loopless directed graph (digraph) with at most one arc from u to v for every pair of vertices u and v of V(D). Given a digraph D, we say that D is 3-quasi-transitive if, whenever u→v→w→z in D, then u and z are adjacent or u=z. In Bang-Jensen (2004) [3], Bang-Jensen introduced 3-quasi-transitive digraphs and claimed that the only strong 3-quasi-transitive digraphs are the strong semicomplete digraphs and strong semicomplete bipartite digraphs. In this paper, we exhibit a family of strong 3-quasi-transitive digraphs distinct from strong semicomplete digraphs and strong semicomplete bipartite digraphs and provide a complete characterization of strong 3-quasi-transitive digraphs.     

On the eccentric distance sum of graphs

The eccentric distance sum is a novel topological index that offers a vast potential for structure activity/property relationships. For a graph G, it is defined as ξd(G)=_∑v∈Vε(v)D(v), where ε(v) is the eccentricity of the vertex v and D(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. Motivated by [G. Yu, L. Feng, A. Ili?, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 934-944], in this paper we characterize the extremal trees and graphs with maximal eccentric distance sum. Various lower and upper bounds for the eccentric distance sum in terms of other graph invariants including the Wiener index, the degree distance, eccentric connectivity index, independence number, connectivity, matching number, chromatic number and clique number are established. In addition, we present explicit formulae for the values of eccentric distance sum for the Cartesian product, applied to some graphs of chemical interest (like nanotubes and nanotori).     

Secure domination critical graphs

A secure dominating set X of a graph G is a dominating set with the property that each vertex u∈V_G−X is adjacent to a vertex v∈X such that (X−{v})∪{u} is dominating. The minimum cardinality of such a set is called the secure domination number, denoted by γ_s(G). We are interested in the effect of edge removal on γ_s(G), and characterize γ_s-ER-critical graphs, i.e. graphs for which γ_s(G−e)>γ_s(G) for any edge e of G, bipartite γ_s-ER-critical graphs and γ_s-ER-critical trees.     

A note on Roman domination in graphs

Let G=(V,E) be a simple graph. A subset S⊆V is a dominating set of G, if for any vertex u∈V-S, there exists a vertex v∈S such that uv∈E. The domination number of G, γ(G), equals the minimum cardinality of a dominating set. A Roman dominating function on graph G=(V,E) is a function f:V→{0,1,2} satisfying the condition that every vertex v for which f(v)=0 is adjacent to at least one vertex u for which f(u)=2. The weight of a Roman dominating function is the value f(V)=∑_v∈Vf(v). The Roman domination number of a graph G, denoted by γ_R(G), equals the minimum weight of a Roman dominating function on G. In this paper, for any integer k(2?k?γ(G)), we give a characterization of graphs for which γ_R(G)=γ(G)+k, which settles an open problem in [E.J. Cockayne, P.M. Dreyer Jr, S.M. Hedetniemi et al. On Roman domination in graphs, Discrete Math. 278 (2004) 11-22].     

Regular graphs are not universal fixers

For any permutation π of the vertex set of a graph G, the graph πG is obtained from two copies G^′ and G^″ of G by joining u∈V(G^′) and v∈V(G^″) if and only if v=π(u). Denote the domination number of G by γ(G). For all permutations π of V(G), γ(G)≤γ(πG)≤2γ(G). If γ(πG)=γ(G) for all π, then G is called a universal fixer. We prove that regular graphs and graphs with γ=4 are not universal fixers.     

On a cyclic connectivity property of directed graphs

Let us call a digraph D cycle-connected if for every pair of vertices u,v∈V(D) there exists a cycle containing both u and v. In this paper we study the following open problem introduced by Ádám. Let D be a cycle-connected digraph. Does there exist a universal edge in D, i.e., an edge e∈E(D) such that for every w∈V(D) there exists a cycle C such that w∈V(C) and e∈E(C)?In his 2001 paper Hetyei conjectured that cycle-connectivity always implies the existence of a universal edge. In the present paper we prove the conjecture of Hetyei for bitournaments.     

Minimum cost homomorphisms to semicomplete multipartite digraphs

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism ofDtoH if uv∈A(D) implies f(u)f(v)∈A(H). For a fixed directed or undirected graph H and an input graph D, the problem of verifying whether there exists a homomorphism of D to H has been studied in a large number of papers. We study an optimization version of this decision problem. Our optimization problem is motivated by a real-world problem in defence logistics and was introduced recently by the authors and M. Tso.Suppose we are given a pair of digraphs D,H and a cost c_i(u) for each u∈V(D) and i∈V(H). The cost of a homomorphism f of D to H is ∑_u∈V(D)c_f(u)(u). Let H be a fixed digraph. The minimum cost homomorphism problem for H, MinHOMP(H), is stated as follows: For input digraph D and costs c_i(u) for each u∈V(D) and i∈V(H), verify whether there is a homomorphism of D to H and, if it does exist, find such a homomorphism of minimum cost. In our previous paper we obtained a dichotomy classification of the time complexity of when H is a semicomplete digraph. In this paper we extend the classification to semicomplete k-partite digraphs, k≥3, and obtain such a classification for bipartite tournaments.     

Every cycle-connected multipartite tournament has a universal arc

A digraph D is cycle-connected if for every pair of vertices u,v∈V(D) there exists a directed cycle in D containing both u and v. In 1999, Ádám [A. Ádám, On some cyclic connectivity properties of directed graphs, Acta Cybernet. 14 (1) (1999) 1-12] posed the following problem. Let D be a cycle-connected digraph. Does there exist a universal arc in D, i.e., an arc e∈A(D) such that for every vertex w∈V(D) there is a directed cycle in D containing both e and w?A c-partite or multipartite tournament is an orientation of a complete c-partite graph. Recently, Hubenko [A. Hubenko, On a cyclic connectivity property of directed graphs, Discrete Math. 308 (2008) 1018-1024] proved that each cycle-connected bipartite tournament has a universal arc. As an extension of this result, we show in this note that each cycle-connected multipartite tournament has a universal arc.     

On CCE graphs of doubly partial orders

Let D be a digraph. The competition-common enemy graph (CCE graph) of D has the same set of vertices as D and an edge between vertices u and v if and only if there are vertices w and x in D such that (w,u), (w,v), (u,x), and (v,x) are arcs of D. We call a graph a CCE graph if it is the CCE graph of some digraph. In this paper, we show that if the CCE graph of a doubly partial order does not contain C₄ as an induced subgraph, it is an interval graph. We also show that any interval graph together with enough isolated vertices is the CCE graph of some doubly partial order.     

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.     

Connected domination of regular graphs

A dominating setD of a graph G is a subset of V(G) such that for every vertex v∈V(G), either v∈D or there exists a vertex u∈D that is adjacent to v in G. Dominating sets of small cardinality are of interest. A connected dominating setC of a graph G is a dominating set of G such that the subgraph induced by the vertices of C in G is connected. A weakly-connected dominating setW of a graph G is a dominating set of G such that the subgraph consisting of V(G) and all edges incident with vertices in W is connected. In this paper we present several algorithms for finding small connected dominating sets and small weakly-connected dominating sets of regular graphs. We analyse the average-case performance of these heuristics on random regular graphs using differential equations, thus giving upper bounds on the size of a smallest connected dominating set and the size of a smallest weakly-connected dominating set of random regular graphs.     

Distance-hereditary graphs and signpost systems

An ordered pair (U,R) is called a signpost system if U is a finite nonempty set, R⊆U×U×U, and the following axioms hold for all u,v,w∈U: (1) if (u,v,w)∈R, then (v,u,u)∈R; (2) if (u,v,w)∈R, then (v,u,w)∉R; (3) if u≠v, then there exists t∈U such that (u,t,v)∈R. (If F is a (finite) connected graph with vertex set U and distance function d, then U together with the set of all ordered triples (u,v,w) of vertices in F such that d(u,v)=1 and d(v,w)=d(u,w)−1 is an example of a signpost system). If (U,R) is a signpost system and G is a graph, then G is called the underlying graph of (U,R) if V(G)=U and xy∈E(G) if and only if (x,y,y)∈R (for all x,y∈U). It is possible to say that a signpost system shows a way how to travel in its underlying graph. The following result is proved: Let (U,R) be a signpost system and let G denote the underlying graph of (U,R). Then G is connected and every induced path in G is a geodesic in G if and only if (U,R) satisfies axioms (4)-(8) stated in this paper; note that axioms (4)-(8)-similarly as axioms (1)-(3)-can be formulated in the language of the first-order logic.     

Minimum cost and list homomorphisms to semicomplete digraphs

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism of D to H if uv∈A(D) implies f(u)f(v)∈A(H). Let H be a fixed directed or undirected graph. The homomorphism problem for H asks whether a directed or undirected input graph D admits a homomorphism to H. The list homomorphism problem for H is a generalization of the homomorphism problem for H, where every vertex x∈V(D) is assigned a set L_x of possible colors (vertices of H).The following optimization version of these decision problems generalizes the list homomorphism problem and was introduced in Gutin et al. [Level of repair analysis and minimum cost homomorphisms of graphs, Discrete Appl. Math., to appear], where it was motivated by a real-world problem in defence logistics. Suppose we are given a pair of digraphs D,H and a positive integral cost c_i(u) for each u∈V(D) and i∈V(H). The cost of a homomorphism f of D to H is . For a fixed digraph H, the minimum cost homomorphism problem for H is stated as follows: for an input digraph D and costs c_i(u) for each u∈V(D) and i∈V(H), verify whether there is a homomorphism of D to H and, if one exists, find such a homomorphism of minimum cost.We obtain dichotomy classifications of the computational complexity of the list homomorphism and minimum cost homomorphism problems, when H is a semicomplete digraph (digraph in which there is at least one arc between any two vertices). Our dichotomy for the list homomorphism problem coincides with the one obtained by Bang-Jensen, Hell and MacGillivray in 1988 for the homomorphism problem when H is a semicomplete digraph: both problems are polynomial solvable if H has at most one cycle; otherwise, both problems are NP-complete. The dichotomy for the minimum cost homomorphism problem is different: the problem is polynomial time solvable if H is acyclic or H is a cycle of length 2 or 3; otherwise, the problem is NP-hard.     

Induced path transit function, monotone and Peano axioms

The induced path transit function J(u,v) in a graph consists of the set of all vertices lying on any induced path between the vertices u and v. A transit function J satisfies monotone axiom if x,y∈J(u,v) implies J(x,y)⊆J(u,v). A transit function J is said to satisfy the Peano axiom if, for any u,v,w∈V,x∈J(v,w), y∈J(u,x), there is a z∈J(u,v) such that y∈J(w,z). These two axioms are equivalent for the induced path transit function of a graph. Planar graphs for which the induced path transit function satisfies the monotone axiom are characterized by forbidden induced subgraphs.     

Degree sum conditions for oriented forests in digraphs

Let F be an oriented forest with n vertices and m arcs and D be a digraph without loops and multiple arcs. In this note we prove that D contains a subdigraph isomorphic to F if D has at least n vertices and min{d⁺(u)+d⁺(v),d⁻(u)+d⁻(v),d⁺(u)+d⁻(v)}≥2m−1 for every pair of vertices u,v∈V(D) with uv∉A(D). This is a common generalization of two results of Babu and Diwan, one on the existence of forests in graphs under a degree sum condition and the other on the existence of oriented forests in digraphs under a minimum degree condition.