The recognition of the class of indecomposable digraphs under low hemimorphy

Given a digraph G=(V,A), the subdigraph of G induced by a subset X of V is denoted by G[X]. With each digraph G=(V,A) is associated its dual G^?=(V,A^?) defined as follows: for any x,y∈V, (x,y)∈A^? if (y,x)∈A. Two digraphs G and H are hemimorphic if G is isomorphic to H or to H^?. Given k>0, the digraphs G=(V,A) and H=(V,B) are k-hemimorphic if for every X⊆V, with |X|≤k, G[X] and H[X] are hemimorphic. A class C of digraphs is k-recognizable if every digraph k-hemimorphic to a digraph of C belongs to C. In another vein, given a digraph G=(V,A), a subset X of V is an interval of G provided that for a,b∈X and x∈V−X, (a,x)∈A if and only if (b,x)∈A, and similarly for (x,a) and (x,b). For example, 0?, {x}, where x∈V, and V are intervals called trivial. A digraph is indecomposable if all its intervals are trivial. We characterize the indecomposable digraphs which are 3-hemimorphic to a non-indecomposable digraph. It follows that the class of indecomposable digraphs is 4-recognizable.     

Tournois infinis et critiques

Given a tournament T=(V,A), a subset X of V is an interval of T provided that for every a,b∈X and x∈V?X, (a,x)∈A if and only if (b,x)∈A. For example, ?, {x} (x∈V) and V are intervals of T, called trivial intervals. A tournament all the intervals of which are trivial is called indecomposable; otherwise, it is decomposable. An indecomposable tournament T=(V,A) is then said to be critical if for each x∈V, T(V?{x}) is decomposable and if there are x≠y∈V such that T(V?{x,y}) is indecomposable. We introduce the operation of expansion which allows us to describe a process of construction of critical and infinite tournaments. It follows that, for every critical and infinite tournament T=(V,A), there are x≠y∈V such that T and T(V?{x,y}) are isomorphic. To cite this article: I. Boudabbous, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

A linear algorithm for minimum 1-identifying codes in oriented trees

Consider an oriented graph G=(V,A), a subset of vertices C⊆V, and an integer r?1; for any vertex v∈V, let denote the set of all vertices x such that there exists a path from x to v with at most r arcs. If for all vertices v∈V, the sets are all nonempty and different, then we call C an r-identifying code. We describe a linear algorithm which gives a minimum 1-identifying code in any oriented tree.     

On the degrees of a strongly vertex-magic graph

Let G=(V,E) be a finite graph, where |V|=n?2 and |E|=e?1. A vertex-magic total labeling is a bijection λ from V∪E to the set of consecutive integers {1,2,…,n+e} with the property that for every v∈V, for some constant h. Such a labeling is strong if λ(V)={1,2,…,n}. In this paper, we prove first that the minimum degree of a strongly vertex-magic graph is at least two. Next, we show that if , then the minimum degree of a strongly vertex-magic graph is at least three. Further, we obtain upper and lower bounds of any vertex degree in terms of n and e. As a consequence we show that a strongly vertex-magic graph is maximally edge-connected and hamiltonian if the number of edges is large enough. Finally, we prove that semi-regular bipartite graphs are not strongly vertex-magic graphs, and we provide strongly vertex-magic total labeling of certain families of circulant graphs.     

Partitioning a graph into alliance free sets

A strong defensive alliance in a graph G=(V,E) is a set of vertices A⊆V, for which every vertex v∈A has at least as many neighbors in A as in V−A. We call a partition A,B of vertices to be an alliance-free partition, if neither A nor B contains a strong defensive alliance as a subset. We prove that a connected graph G has an alliance-free partition exactly when G has a block that is other than an odd clique or an odd cycle.     

Small alliances in a weighted graph

We extend the notion of a defensive alliance to weighted graphs. Let (G,w) be a weighted graph, where G is a graph and w be a function from V(G) to the set of positive real numbers. A non-empty set of vertices S in G is said to be a weighted defensive alliance if ∑_{x∈NG(v)∩S}w(x)+w(v)≥∑_{x∈NG(v)−S}w(x) holds for every vertex v in S. Fricke et al. (2003) [3] have proved that every graph of order n has a defensive alliance of order at most . In this note, we generalize this result to weighted defensive alliances. Let G be a graph of order n. Then we prove that for any weight function w on V(G), (G,w) has a defensive weighted alliance of order at most . We also extend the notion of strong defensive alliance to weighted graphs and generalize a result in Fricke et al. (2003) [3].     

On 2-factors with cycles containing specified edges in a bipartite graph

Let k≥1 be an integer and G=(V₁,V₂;E) a bipartite graph with |V₁|=|V₂|=n such that n≥2k+2. In this paper it has been proved that if for each pair of nonadjacent vertices x∈V₁ and y∈V₂, , then for any k independent edges e₁,…,e_k of G, G has a 2-factor with k+1 cycles C₁,…,C_k+1 such that e_i∈E(C_i) and |V(C_i)|=4 for each i∈{1,…,k}. We shall also show that the conditions in this paper are sharp.     

Factors and vertex-deleted subgraphs

A relationship is considered between an f-factor of a graph and that of its vertex-deleted subgraphs. Katerinis [Some results on the existence of 2n-factors in terms of vertex-deleted subgraphs, Ars Combin. 16 (1983) 271-277] proved that for even integer k, if G-x has a k-factor for each x∈V(G), then G has a k-factor. Enomoto and Tokuda [Complete-factors and f-factors, Discrete Math. 220 (2000) 239-242] generalized Katerinis’ result to f-factors, and proved that if G-x has an f-factor for each x∈V(G), then G has an f-factor for an integer-valued function f defined on V(G) with even. In this paper, we consider a similar problem to that of Enomoto and Tokuda, where for several vertices x we do not have to know whether G-x has an f-factor. Let G be a graph, X be a set of vertices, and let f be an integer-valued function defined on V(G) with even, |V(G)-X|?2. We prove that if and if G-x has an f-factor for each x∈V(G)-X, then G has an f-factor. Moreover, if G excludes an isolated vertex, then we can replace the condition with . Furthermore the condition will be when |X|=1.     

On the Roman domination number of a graph

A Roman dominating function of a graph G is a labeling f:V(G)?{0,1,2} such that every vertex with label 0 has a neighbor with label 2. The Roman domination number γ_R(G) of G is the minimum of ∑_v∈V(G)f(v) over such functions. A Roman dominating function of G of weight γ_R(G) is called a γ_R(G)-function. A Roman dominating function f:V?{0,1,2} can be represented by the ordered partition (V₀,V₁,V₂) of V, where V_i={v∈V∣f(v)=i}. Cockayne et al. [E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, S.T. Hedetniemi, On Roman domination in graphs, Discrete Math. 278 (2004) 11-22] posed the following question: What can we say about the minimum and maximum values of |V₀|,|V₁|,|V₂| for a γ_R-function f=(V₀,V₁,V₂) of a graph G? In this paper we first show that for any connected graph G of order n≥3, , where γ(G) is the domination number of G. Also we prove that for any γ_R-function f=(V₀,V₁,V₂) of a connected graph G of order n≥3, , and .     

Solutions of polynomial Pell's equation

Let D=F²+2G be a monic quartic polynomial in Z[x], where . Then for F/G∈Q[x], a necessary and sufficient condition for the solution of the polynomial Pell's equation X²−DY²=1 in Z[x] has been shown. Also, the polynomial Pell's equation X²−DY²=1 has nontrivial solutions X,Y∈Q[x] if and only if the values of period of the continued fraction of are 2, 4, 6, 8, 10, 14, 18, and 22 has been shown. In this paper, for the period of the continued fraction of is 4, we show that the polynomial Pell's equation has no nontrivial solutions X,Y∈Z[x].     

The exact domination number of the generalized Petersen graphs

Let G=(V,E) be a graph. A subset S⊆V is a dominating set of G, if every vertex u∈V−S is dominated by some vertex v∈S. The domination number, denoted by γ(G), is the minimum cardinality of a dominating set. For the generalized Petersen graph G(n), Behzad et al. [A. Behzad, M. Behzad, C.E. Praeger, On the domination number of the generalized Petersen graphs, Discrete Mathematics 308 (2008) 603-610] proved that and conjectured that the upper bound is the exact domination number. In this paper we prove this conjecture.     

An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree

Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γ_r(G), is the smallest cardinality of a restrained dominating set of G. We will show that if G is a connected graph of order n and minimum degree δ and not isomorphic to one of nine exceptional graphs, then .     

Bounds on a graph's security number

Let G=(V,E) be a graph. A set S⊆V is a defensive alliance if |N[x]∩S|?|N[x]-S| for every x∈S. Thus, each vertex of a defensive alliance can, with the aid of its neighbors in S, be defended from attack by its neighbors outside of S. An entire set S is secure if any subset X⊆S, not just singletons, can be defended from an attack from outside of S, under an appropriate definition of what such a defense implies. The security number s(G) of G is the cardinality of a smallest secure set. Bounds on s(G) are presented.     

Critically indecomposable graphs

An undirected graph G=(V,E) with a specific subset X⊂V is called X-critical if G and G(X), induced subgraph on X, are indecomposable but G(V−{w}) is decomposable for every w∈V−X. This is a generalization of critically indecomposable graphs studied by Schmerl and Trotter [J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics 113 (1993) 191-205] and Bonizzoni [P. Bonizzoni, Primitive 2-structures with the (n−2)-property, Theoretical Computer Science 132 (1994) 151-178], who deal with the case where X is empty.We present several structural results for this class of graphs and show that in every X-critical graph the vertices of V−X can be partitioned into pairs (a₁,b₁),(a₂,b₂),…,(a_m,b_m) such that G(V−{a_j1,b_j1,…,a_jk,b_jk}) is also an X-critical graph for arbitrary set of indices {j₁,…,j_k}. These vertex pairs are called commutative elimination sequence. If G is an arbitrary indecomposable graph with an indecomposable induced subgraph G(X), then the above result establishes the existence of an indecomposability preserving sequence of vertex pairs (x₁,y₁),…,(x_t,y_t) such that x_i,y_i∈V−X. As an application of the commutative elimination sequence of an X-critical graph we present algorithms to extend a 3-coloring (similarly, 1-factor) of G(X) to entire G.     

The signed domatic number of some regular graphs

Let G be a finite and simple graph with vertex set V(G), and let f:V(G)→{−1,1} be a two-valued function. If ∑_x∈N[v]f(x)≥1 for each v∈V(G), where N[v] is the closed neighborhood of v, then f is a signed dominating function on G. A set {f₁,f₂,…,f_d} of signed dominating functions on G with the property that for each x∈V(G), is called a signed dominating family (of functions) on G. The maximum number of functions in a signed dominating family on G is the signed domatic number on G. In this paper, we investigate the signed domatic number of some circulant graphs and of the torus C_p×C_q.     

A better approximation algorithm for the budget prize collecting tree problem

Given an undirected graph G=(V,E), an edge cost c(e)?0 for each edge e∈E, a vertex prize p(v)?0 for each vertex v∈V, and an edge budget B. The BUDGET PRIZE COLLECTING TREE PROBLEM is to find a subtree T′=(V′,E′) that maximizes , subject to . We present a (4+ε)-approximation algorithm.     

The evolution of the min-min random graph process

We study the following min-min random graph process G=(G₀,G₁,…): the initial state G₀ is an empty graph on n vertices (n even). Further, G_M+1 is obtained from G_M by choosing a pair {v,w} of distinct vertices of minimum degree uniformly at random among all such pairs in G_M and adding the edge {v,w}. The process may produce multiple edges. We show that G_M is asymptotically almost surely disconnected if M≤n, and that for M=(1+t)n, constant, the probability that G_M is connected increases from 0 to 1. Furthermore, we investigate the number X of vertices outside the giant component of G_M for M=(1+t)n. For constant we derive the precise limiting distribution of X. In addition, for n⁻¹ln⁴n≤t=o(1) we show that tX converges to a gamma distribution.