On island sequences of labelings with a condition at distance two

An L(2,1)-labeling of a graph G is a function f from the vertex set of G to the set of nonnegative integers such that |f(x)−f(y)|≥2 if d(x,y)=1, and |f(x)−f(y)|≥1 if d(x,y)=2, where d(x,y) denotes the distance between the pair of vertices x,y. The lambda number of G, denoted λ(G), is the minimum range of labels used over all L(2,1)-labelings of G. An L(2,1)-labeling of G which achieves the range λ(G) is referred to as a λ-labeling. A hole of an L(2,1)-labeling is an unused integer within the range of integers used. The hole index of G, denoted ρ(G), is the minimum number of holes taken over all its λ-labelings. An island of a given λ-labeling of G with ρ(G) holes is a maximal set of consecutive integers used by the labeling. Georges and Mauro [J.P. Georges, D.W. Mauro, On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] inquired about the existence of a connected graph G with ρ(G)≥1 possessing two λ-labelings with different ordered sequences of island cardinalities. This paper provides an infinite family of such graphs together with their lambda numbers and hole indices. Key to our discussion is the determination of the path covering number of certain 2-sparse graphs, that is, graphs containing no pair of adjacent vertices of degree greater than 2.     

On the hole index of L(2,1)-labelings of r-regular graphs

An L(2,1)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G so that adjacent vertices get labels at least distance two apart and vertices at distance two get distinct labels. A hole is an unused integer within the range of integers used by the labeling. The lambda number of a graph G, denoted λ(G), is the minimum span taken over all L(2,1)-labelings of G. The hole index of a graph G, denoted ρ(G), is the minimum number of holes taken over all L(2,1)-labelings with span exactly λ(G). Georges and Mauro [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] conjectured that if G is an r-regular graph and ρ(G)?1, then ρ(G) must divide r. We show that this conjecture does not hold by providing an infinite number of r-regular graphs G such that ρ(G) and r are relatively prime integers.     

On generalized Petersen graphs labeled with a condition at distance two

An L(2,1)-labeling of graph G is an integer labeling of the vertices in V(G) such that adjacent vertices receive labels which differ by at least two, and vertices which are distance two apart receive labels which differ by at least one. The λ-number of G is the minimum span taken over all L(2,1)-labelings of G. In this paper, we consider the λ-numbers of generalized Petersen graphs. By introducing the notion of a matched sum of graphs, we show that the λ-number of every generalized Petersen graph is bounded from above by 9. We then show that this bound can be improved to 8 for all generalized Petersen graphs with vertex order >12, and, with the exception of the Petersen graph itself, improved to 7 otherwise.     

An extremal problem on non-full colorable graphs

For a given graph G of order n, a k-L(2,1)-labelling is defined as a function f:V(G)→{0,1,2,…k} such that |f(u)-f(v)|?2 when d_G(u,v)=1 and |f(u)-f(v)|?1 when d_G(u,v)=2. The L(2,1)-labelling number of G, denoted by λ(G), is the smallest number k such that G has a k-L(2,1)-labelling. The hole index ρ(G) of G is the minimum number of integers not used in a λ(G)-L(2,1)-labelling of G. We say G is full-colorable if ρ(G)=0; otherwise, it will be called non-full colorable. In this paper, we consider the graphs with λ(G)=2m and ρ(G)=m, where m is a positive integer. Our main work generalized a result by Fishburn and Roberts [No-hole L(2,1)-colorings, Discrete Appl. Math. 130 (2003) 513-519].     

Distance-two labelings of digraphs

For positive integers j?k, an L(j,k)-labeling of a digraph D is a function f from V(D) into the set of nonnegative integers such that |f(x)-f(y)|?j if x is adjacent to y in D and |f(x)-f(y)|?k if x is of distance two to y in D. Elements of the image of f are called labels. The L(j,k)-labeling problem is to determine the -number of a digraph D, which is the minimum of the maximum label used in an L(j,k)-labeling of D. This paper studies -numbers of digraphs. In particular, we determine -numbers of digraphs whose longest dipath is of length at most 2, and -numbers of ditrees having dipaths of length 4. We also give bounds for -numbers of bipartite digraphs whose longest dipath is of length 3. Finally, we present a linear-time algorithm for determining -numbers of ditrees whose longest dipath is of length 3.     

Strong edge-magic graphs of maximum size

An edge-magic total labeling on G is a one-to-one map λ from V(G)∪E(G) onto the integers 1,2,…,|V(G)∪E(G)| with the property that, given any edge (x,y), λ(x)+λ(x,y)+λ(y)=k for some constant k. The labeling is strong if all the smallest labels are assigned to the vertices. Enomoto et al. proved that a graph admitting a strong labeling can have at most 2|V(G)|-3 edges. In this paper we study graphs of this maximum size.     

Labeling bipartite permutation graphs with a condition at distance two

An L(p,q)-labeling of a graph G is an assignment f from vertices of G to the set of non-negative integers {0,1,…,λ} such that |f(u)−f(v)|≥p if u and v are adjacent, and |f(u)−f(v)|≥q if u and v are at distance 2 apart. The minimum value of λ for which G has L(p,q)-labeling is denoted by λ_p,q(G). The L(p,q)-labeling problem is related to the channel assignment problem for wireless networks.In this paper, we present a polynomial time algorithm for computing L(p,q)-labeling of a bipartite permutation graph G such that the largest label is at most (2p−1)+q(bc(G)−2), where bc(G) is the biclique number of G. Since λ_p,q(G)≥p+q(bc(G)−2) for any bipartite graph G, the upper bound is at most p−1 far from optimal.     

Non-Separating Paths in 4-Connected Graphs

In 1975, Lovász conjectured that for any positive integer k, there exists a minimum positive integer f(k) such that, for any two vertices x, y in any f(k)-connected graph G, there is a path P from x to y in G such that G–V(P) is k-connected. A result of Tutte implies f(1) = 3. Recently, f(2) = 5 was shown by Chen et al. and, independently, by Kriesell. In this paper, we show that f(2) = 4 except for double wheels.Received October 17, 2003     

Graphs with small boundary

For a pair of vertices x and y in a graph G, we denote by d_G(x,y) the distance between x and y in G. We call x a boundary vertex of y if x and y belong to the same component and d_G(y,v)?d_G(y,x) for each neighbor v of x in G. A boundary vertex of some vertex is simply called a boundary vertex, and the set of boundary vertices in G is called the boundary of G, and is denoted by B(G).In this paper, we investigate graphs with a small boundary. Since a pair of farthest vertices are boundary vertices, |B(G)|?2 for every connected graph G of order at least two. We characterize the graphs with boundary of order at most three. We cannot give a characterization of graphs with exactly four boundary vertices, but we prove that such graphs have minimum degree at most six. Finally, we give an upper bound to the minimum degree of a connected graph G in terms of |B(G)|.     

A comparative study of functional equations characterising sine and cosine

A comparative study of the functional equationsf(x+y)f(x–y)=f ²(x)–f ²(y),f(y){f(x+y)+f(x–y)}=f(x)f(2y) andf(x+y)+f(x–y)=2f(x){1–2f ²(y/2)} which characterise the sine function has been carried out. The zeros of the functionf satisfying any one of the above equations play a vital role in the investigations. The relation of the equationf(x+y)+f(x–y)=2f(x){1–2f ²(y/2)} with D'Alembert's equation,f(x+y)+f(x–y)=2f(x)f(y) and the sine-cosine equationg(x–y)=g(x)g(y) +f(x)f(y) has also been investigated.     

A survey on labeling graphs with a condition at distance two

For positive integers k,d₁,d₂, a k-L(d₁,d₂)-labeling of a graph G is a function f:V(G)→{0,1,2,…,k} such that |f(u)-f(v)|?d_i whenever the distance between u and v is i in G, for i=1,2. The L(d₁,d₂)-number of G, λ_d1,d2(G), is the smallest k such that there exists a k-L(d₁,d₂)-labeling of G. This class of labelings is motivated by the code (or frequency) assignment problem in computer network. This article surveys the results on this labeling problem.     

Labeling graphs with two distance constraints

Given a graph G and integers p,q,d₁ and d₂, with p>q, d₂>d₁?1, an L(d₁,d₂;p,q)-labeling of G is a function f:V(G)→{0,1,2,…,n} such that |f(u)−f(v)|?p if d_G(u,v)?d₁ and |f(u)−f(v)|?q if d_G(u,v)?d₂. A k-L(d₁,d₂;p,q)-labeling is an L(d₁,d₂;p,q)-labeling f such that max_v∈V(G)f(v)?k. The L(d₁,d₂;p,q)-labeling number ofG, denoted by , is the smallest number k such that G has a k-L(d₁,d₂;p,q)-labeling. In this paper, we give upper bounds and lower bounds of the L(d₁,d₂;p,q)-labeling number for general graphs and some special graphs. We also discuss the L(d₁,d₂;p,q)-labeling number of G, when G is a path, a power of a path, or Cartesian product of two paths.     

On the parity of the partition function

Let N be the set of all positive integers and D a subset of N. Let p(D,n) be the number of partitions of n with parts in D and let |D(x)| denote the number of elements of D not exceeding x. It is proved that if D is an infinite subset of N such that p(D,n) is even for all n?n₀, then |D(x)|?logx/log2−logn₀/log2. Moreover, if D is an infinite subset of N such that p(D,n) is odd for all n?n₀ and , then |D(x)|?logx/log2−logn₀/log2. These lower bounds are essentially the best possible.     

Subpancyclicity of line graphs and degree sums along paths

A graph is called subpancyclic if it contains a cycle of length ? for each ? between 3 and the circumference of the graph. We show that if G is a connected graph on n?146 vertices such that d(u)+d(v)+d(x)+d(y)>(n+10/2) for all four vertices u,v,x,y of any path P=uvxy in G, then the line graph L(G) is subpancyclic, unless G is isomorphic to an exceptional graph. Moreover, we show that this result is best possible, even under the assumption that L(G) is hamiltonian. This improves earlier sufficient conditions by a multiplicative factor rather than an additive constant.     

On Bernstein's inequality for entire functions of exponential type

It was shown by S.N. Bernstein that if f is an entire function of exponential type τ such that |f(x)|?M for −∞<x<∞, then |f^′(x)|?Mτ for −∞<x<∞. If p is a polynomial of degree at most n with |p(z)|?M for |z|=1, then f(z):=p(eiz) is an entire function of exponential type n with |f(x)|?M on the real axis. Hence, by the just mentioned inequality for functions of exponential type, |p^′(z)|?Mn for |z|=1. Lately, many papers have been written on polynomials p that satisfy the condition znp(1/z)≡p(z). They do form an intriguing class. If a polynomial p satisfies this condition, then f(z):=p(eiz) is an entire function of exponential type n that satisfies the condition f(z)≡einzf(−z). This led Govil [N.K. Govil, Lp inequalities for entire functions of exponential type, Math. Inequal. Appl. 6 (2003) 445-452] to consider entire functions f of exponential type satisfying f(z)≡eiτzf(−z) and find estimates for their derivatives. In the present paper we present some additional observations about such functions.     

The convexity spectra of graphs

Let D be a connected oriented graph. A set S⊆V(D) is convex in D if, for every pair of vertices x,y∈S, the vertex set of every x-y geodesic (x-y shortest dipath) and y-x geodesic in D is contained in S. The convexity numbercon(D) of a nontrivial oriented graph D is the maximum cardinality of a proper convex set of D. Let G be a graph. We define that S_C(G)={con(D):D is an orientation of G} and S_SC(G)={con(D):D is a strongly connected orientation of G}. In the paper, we show that, for any n?4, 1?a?n-2, and a≠2, there exists a 2-connected graph G with n vertices such that S_C(G)=S_SC(G)={a,n-1} and there is no connected graph G of order n?3 with S_SC(G)={n-1}. Then, we determine that S_C(K₃)={1,2}, S_C(K₄)={1,3}, S_SC(K₃)=S_SC(K₄)={1}, S_C(K₅)={1,3,4}, S_C(K₆)={1,3,4,5}, S_SC(K₅)=S_SC(K₆)={1,3}, S_C(K_n)={1,3,5,6,…,n-1}, S_SC(K_n)={1,3,5,6,…,n-2} for n?7. Finally, we prove that, for any integers n, m, and k with , 1?k?n-1, and k≠2,4, there exists a strongly connected oriented graph D with n vertices, m edges, and convexity number k.     

Stability of a simple Levi–Civitá functional equation on non-unital commutative semigroups

In this paper, we study the Hyers–Ulam stability of a simple Levi–Civitá functional equation f(x+y)=f(x)h(y)+f(y) and its pexiderization f(x+y)= g(x) h(y)+k(y) on non-unital commutative semigroups by investigating the functional inequalities |f(x+y)?f(x)h(y)?f(y)|≤?? and |f(x+y)?g(x)h(y)?k(y)|≤??, respectively. We also study the bounded solutions of the simple Levi–Civitá functional inequality.     

Groups whose nonlinear irreducible characters separate element orders or conjugacy class sizes

A class function φ on a finite group G is said to be an order separator if, for every x and y in G \ {1}, φ(x) = φ(y) is equivalent to x and y being of the same order. Similarly, φ is said to be a class-size separator if, for every x and y in G\ {1}, φ(x) = φ(y) is equivalent to |C _G (x)| = |C _G (y)|. In this paper, finite groups whose nonlinear irreducible complex characters are all order separators (respectively, class-size separators) are classified. In fact, a more general setting is studied, from which these classifications follow. This analysis has some connections with the study of finite groups such that every two elements lying in distinct conjugacy classes have distinct orders, or, respectively, in which disctinct conjugacy classes have distinct sizes. Received: 10 April 2007     

A general class of fuzzy operators,the demorgan class of fuzzy operators and fuzziness measures induced by fuzzy operators

In this paper we examine operators which can be derived from the general solution of functional equations on associativity. We define the characteristics of those functions f(x) which are necessary for the production of operators. We shall show, that with the help of the negation operator for every such function f(x) a function g(x) can be given, from which a disjunctive operator can be derived, and for the three operators the DeMorgan identity is fulfilled. For the fulfillment of the DeMorgan identity the necessary and sufficient conditions are given.We shall also show that an f_λ(x) can be constructed for every f(x), so that for the derived k_λ(x,y) and d_λ(x,y) lim_λ→∞k_λ(x,y) and lim_λ→∞d_λ(x,y) = max(x,y).As Yager's operator is not reducible, for every λ there exists an α, for which, in case x < α and y<α, k_λ(x,y) = 0.We shall give an f(x) which has the characteristics of Yager's operator, and which is strictly monotone.Finally we shall show, that with the help of all those f(x), which are necessary when constructing a k(x,y), an F(x) can be constructed which has the properties of the measures of fuzziness introduced by A. De Luca and S. Termini. Some classical fuzziness measures are obtained as special cases of our system.     

The elimination procedure for the competition number is not optimal

Given an acyclic digraph D, the competition graph C(D) is defined to be the undirected graph with V(D) as its vertex set and where vertices x and y are adjacent if there exists another vertex z such that the arcs (x,z) and (y,z) are both present in D. The competition number k(G) for an undirected graph G is the least number r such that there exists an acyclic digraph F on |V(G)|+r vertices where C(F) is G along with r isolated vertices. Kim and Roberts [The Elimination Procedure for the Competition Number, Ars Combin. 50 (1998) 97-113] introduced an elimination procedure for the competition number, and asked whether the procedure calculated the competition number for all graphs. We answer this question in the negative by demonstrating a graph where the elimination procedure does not calculate the competition number. This graph also provides a negative answer to a similar question about the related elimination procedure for the phylogeny number introduced by the current author in [S.G. Hartke, The Elimination Procedure for the Phylogeny Number, Ars Combin. 75 (2005) 297-311].