Search

*Correspondence: wadade@se.kanazawa-u.ac.jp 3Faculty of Mechanical Engineering, Institute of Science and Engineering, Kanazawa University, Kakuma, Kanazawa, Ishikawa 920-1192, Japan Full list of author information is available at the end of the article The purpose of this note is to clarify the novelty of the paper entitled ‘Generalizations of the logarithmic Hardy inequality in critical Sobolev-Lorentz spaces’ which was published in the J. Inequal. Appl. :,  []. After this paper was published, the authors were informed of the references [–], and [], the results of which partly overlap with those of []. In the paper [], the authors established the Hardy inequality of the logarithmic type in the critical Sobolev-Lorentz spaces H n p p,q(R); see Section  in [] for the precise definition of H n p p,q(R). The main theorem in [] is stated as follows. Theorem A [, Theorem .] Let n ∈ N,  < p

Zannier proved that for a Laurent series f(x) satisfying the functional equation of type f(x m ) = P(x, f(x)), where \( P(x, y) \in {\Bbb C}(x)[y] \), if f(x) is not rational the set of such m consists of the powers of a single integer. He mentioned that the case f(x) = P(x, f(x m )) should be proved in a similar way. In this paper we first verify this statement and second we show a theorem which is useful for proving the transcendence of a Laurent series satisfying a certain functional equation. This theorem is a generalization of the result that a Laurent series which satisfiesf(x m ) = P(x, f(x)), where\( P(x, y) \in {\Bbb C}(x, y),\,m \geq 2 \)cannot represent an algebraic function unless it is rational (Ke. Nishioka [1], Zannier [8], Section 3).

Solomon and Elkin (SIAM J Discret Math 28(3):1173–1198, 2014) constructed a shortcutting scheme for weighted trees which results in a 1-spanner for the tree metric induced by the input tree. The spanner has logarithmic lightness, logarithmic diameter, a linear number of edges and bounded degree (provided the input tree has bounded degree). This spanner has been applied in a series of papers devoted to designing bounded degree, low-diameter, low-weight $$(1+\epsilon )$$ -spanners in Euclidean and doubling metrics. In this paper, we present a simple local routing algorithm for this tree metric spanner. The algorithm has a routing ratio of 1, is guaranteed to terminate after $$O(\log n)$$ hops and requires $$O(\varDelta \log n)$$ bits of storage per vertex where $$\varDelta $$ is the maximum degree of the tree on which the spanner is constructed. This local routing algorithm can be adapted to a local routing algorithm for a doubling metric spanner which makes use of the shortcutting scheme.

In this paper we propose a generalized Roman domination problem called connected strong k-Roman dominating set problem. It is NP-hard even in a unit ball graph. Unit ball graphs are the intersection graphs of equal sized balls in the three-dimensional space, they are widely used as a mathematical model for wireless sensor networks and some problems in computational geometry. This paper presents the first constant approximation algorithm with a guaranteed performance ratio at most $$6(k+2)$$ in unit ball graphs, where k is a positive integer.

The Hermite–Hadamard inequality was extended using iterated integrals by Retkes [Acta Sci Math (Szeged) 74:95–106, 2008]. In this paper we further extend the main results of the above paper for convex and also for s-convex functions in the second sense.

One-way Hamming network H(n, 3), namely directed Hamming network, is the cartesian product of n complete graphs $$K_{3}$$ and has been widely used in hypercube parallel computer for its high communication rate and availability. As one of the critical parameters for evaluating the one-way Hamming network performance, the transmission latency which is the time for the information transmits from the source to the destination is proportional to the network diameter, and it can be reduced by optimizing the network diameter, especially, the minimum transmission latency corresponds to the oriented diameter which is the minimum diameter of one-way network. Currently, although the problems in the design and optimization of H(n, 2) with the oriented diameter and the minimum transmission latency have been solved, studies on the one-way Hamming network H(n, 3) are not found the best of our knowledge. This paper studies the one-way Hamming network H(n, 3) with the possible oriented diameter and the possible minimum transmission latency. Specifically, we first present a lemma and a mathematical model for the one-way Hamming network H(n, 3) with the possible oriented diameter and the possible minimum transmission latency, and then propose a recursive method to obtain $$n\le \overrightarrow{d}(H(n,3))\le n+1$$, where $$\overrightarrow{d}(H(n,3))$$ denotes the oriented diameter of H(n, 3). Finally, a practical example is utilized to intuitively describe such a method in this paper. Results show that the optimal design of the one-way Hamming network H(n, 3) helps reduce the information transmission latency by $$100\%$$ as n tends to infinity when 2n is the baseline.

In this paper our aim is to show some new inequalities of the Redheffer type for Bessel and modified Bessel functions of the first kind. The key tools in our proofs are some classical results on the monotonicity of quotients of differentiable functions as well as on the monotonicity of quotients of two power series. We also use some known results on the quotients of Bessel and modified Bessel functions of the first kind, and by using the monotonicity of the Dirichlet eta function we prove a sharp inequality for the tangent function. At the end of the paper a conjecture is stated, which may be of interest for further research.

This paper studies the continuous connected 2-facility location problem (CC2FLP) in trees. Let $$T = (V, E, c, d, \ell , \mu )$$ be an undirected rooted tree, where each node $$v \in V$$ has a weight $$d(v) \ge 0$$ denoting the demand amount of v as well as a weight $$\ell (v) \ge 0$$ denoting the cost of opening a facility at v, and each edge $$e \in E$$ has a weight $$c(e) \ge 0$$ denoting the cost on e and is associated with a function $$\mu (e,t) \ge 0$$ denoting the cost of opening a facility at a point x(e, t) on e where t is a continuous variable on e. Given a subset $$\mathcal {D} \subseteq V$$ of clients, and a subset $$\mathcal {F} \subseteq \mathcal {P}(T)$$ of continuum points admitting facilities where $$\mathcal {P}(T)$$ is the set of all the points on edges of T, when two facilities are installed at a pair of continuum points $$x_1$$ and $$x_2$$ in $$\mathcal {F}$$ , the total cost involved in CC2FLP includes three parts: the cost of opening two facilities at $$x_1$$ and $$x_2$$ , K times the cost of connecting $$x_1$$ and $$x_2$$ , and the cost of all the clients in $$\mathcal {D}$$ connecting to some facility. The objective is to open two facilities at a pair of continuum points in $$\mathcal {F}$$ to minimize the total cost, for a given input parameter $$K \ge 1$$ . This paper focuses on the case of $$\mathcal {D} = V$$ and $$\mathcal {F} = \mathcal {P}(T)$$ . We first study the discrete version of CC2FLP, named the discrete connected 2-facility location problem (DC2FLP), where two facilities are restricted to the nodes of T, and devise a quadratic time edge-splitting algorithm for DC2FLP. Furthermore, we prove that CC2FLP is almost equivalent to DC2FLP in trees, and develop a quadratic time exact algorithm based on the edge-splitting algorithm. Finally, we adapt our algorithms to the general case of $$\mathcal {D} \subseteq V$$ and $$\mathcal {F} \subseteq \mathcal {P}(T)$$ .

The goal of this paper is to point out that the results obtained in the recent papers (Chen and Song in Nonlinear Anal 72:1895–1901, 2010; Chu in J Math Anal Appl 327:1041–1045, 2007; Chu et al. in Nonlinear Anal 59:1001–1011, 2004a, J. Math Anal Appl 289:666–672, 2004b) can be seriously strengthened in the sense that we can significantly relax the assumptions of the main results so that we still get the same conclusions. In order to do this first, we prove that for $$n \ge 3$$ any transformation which preserves the n-norm of any n vectors is automatically plus-minus linear. This will give a re-proof of the well-known Mazur–Ulam-type result that every n-isometry is automatically affine ( $$n \ge 2$$ ) which was proven in several papers, e.g. in Chu et al. (Nonlinear Anal 70:1068–1074, 2009). Second, following the work of Rassias and Semrl (Proc Am Math Soc 118:919–925, 1993), we provide the solution of a natural Aleksandrov-type problem in n-normed spaces, namely, we show that every surjective transformation which preserves the unit n-distance in both directions ( $$n\ge 2$$ ) is automatically an n-isometry.

In this paper we investigate the existence of homoclinic solutions for the following p-Laplacian Hamiltonian systems $$\begin{aligned} \frac{d}{dt}(|{\dot{u}}(t)|^{p-2} {\dot{u}}(t))-a(t)|u(t)|^{p-2}u(t)+\nabla W(t,u(t))=0, \end{aligned}$$ where $$t\in {\mathbb R}$$ , $$u\in {\mathbb R}^n$$ , $$p>1$$ , $$a\in C({\mathbb R},{\mathbb R})$$ , $$W\in C^1({\mathbb R}\times {\mathbb R}^n,{\mathbb R})$$ and $$\nabla W(t,u)$$ is the gradient of W(t, u) in u. The novelty of this paper is that, assuming that a(t) is bounded in the sense that there are two constants $$0

In this paper, we study the minimum partial set multi-cover problem (PSMC). Given an element set E, a collection of subsets \({\mathcal {S}}\subseteq 2^E\), a cost \(c_S\) on each set \(S\in {\mathcal {S}}\), a covering requirement \(r_e\) for each element \(e\in E\), and an integer k, the PSMC problem is to find a sub-collection \({\mathcal {F}}\subseteq {\mathcal {S}}\) to fully cover at least k elements such that the cost of \({\mathcal {F}}\) is as small as possible, where element e is fully covered by \({\mathcal {F}}\) if it belongs to at least \(r_e\) sets of \({\mathcal {F}}\). This paper presents an approximation algorithm using local ratio method achieving performance ratio \(\max \left\{ \frac{\Delta }{k}\left( \frac{1}{f-r_{\min }}+\frac{r_{\max }}{r_{\min }}\right) ,\frac{1}{\rho }+\frac{f}{r_{\min }}+\frac{1}{r_{\max }}-\frac{1}{\rho r_{\max }}-1,\frac{1}{\rho }\right\} \), where \(\Delta \) is the size of a maximum set, f is the maximum number of sets containing a common element, \(\rho \) is the minimum percentage of elements required to be fully covered during iterations of the algorithm, and \(r_{\max }\) and \(r_{\min }\) are the maximum and the minimum covering requirement, respectively. In particular, when \(r_{\max }\) is a constant, the first term can be omitted. Notice that our ratio coincides with the classic ratio f for both the set multi-cover problem (in which case \(k=|E|\)) and the partial set single-cover problem (in which case \(r_{\max }=1\)). However, when \(k 1\), the ratio might be as large as \(\Theta (n)\). This result shows an interesting “shock wave like” feature of approximating PSMC. The purpose of this paper is trying to arouse some interest in such a feature and attract more work on this challenging problem.

The popular matching problem introduced by Abraham, Irving, Kavitha, and Mehlhorn is a matching problem in which there exist applicants and posts, and applicants have preference lists over posts. A matching M is said to be popular, if there exists no other matching N such that the number of applicants that prefer N to M is larger than the number of applicants that prefer M to N. The goal of this problem is to decide whether there exists a popular matching, and find a popular matching if one exists. In this paper, we first consider a matroid generalization of the popular matching problem with strict preference lists, and give a polynomial-time algorithm for this problem. In the second half of this paper, we consider the problem of transforming a given instance of a matroid generalization of the popular matching problem with strict preference lists by deleting a minimum number of applicants so that it has a popular matching. This problem is a matroid generalization of the popular condensation problem with strict preference lists introduced by Wu, Lin, Wang, and Chao. By using the results in the first half, we give a polynomial-time algorithm for this problem.

The notion of statistical weighted $\mathcal{B}$ -summability was introduced very recently (Kadak et al. in Appl. Math. Comput. 302:80–96, 2017). In the paper, we study the concept of statistical deferred weighted $\mathcal{B}$ -summability and deferred weighted $\mathcal{B}$ -statistical convergence and then establish an inclusion relation between them. In particular, based on our proposed methods, we establish a new Korovkin-type approximation theorem for the functions of two variables defined on a Banach space $C_{B}(\mathcal{D})$ and then present an illustrative example to show that our result is a non-trivial extension of some traditional and statistical versions of Korovkin-type approximation theorems which were demonstrated in the earlier works. Furthermore, we establish another result for the rate of deferred weighted $\mathcal{B}$ -statistical convergence for the same set of functions via modulus of continuity. Finally, we consider a number of interesting special cases and illustrative examples in support of our findings of this paper.

Co-path Set problem is of important applications in mapping unique DNA sequences onto chromosomes and whole genomes. Given a graph G, the parameterized version of Co-path Set problem is to find a subset F of edges with size at most k such that each connected component in $$G[E\backslash F]$$G[E\F] is a path. In this paper, we give a kernel of size 6k and a randomized algorithm of running time $$O^*(2.17^k)$$Oź(2.17k) for the Parameterized Co-path Set problem. The randomized methods developed in the paper are of great promising to be applied to other branch-based algorithms.

In this paper we consider a uniform extremal Volterra quadratic stochastic operator defined on an even-dimensional unit simplex, which corresponds to a balanced digraph, and show that such operator has the non-ergodicity property. We also reinterpret this result in the framework of zero-sum games obtaining that these operators correspond to rock-paper-scissors games.

In this paper, we study the following Chromatic kernel (CK) problem: given an $$n$$n-partite graph (called a chromatic correlation graph) $$G=(V,E)$$G=(V,E) with $$V=V_{1}\bigcup \cdots \bigcup V_{n}$$V=V1???Vn and each partite set $$V_{i}$$Vi containing a constant number $$\lambda $$? of vertices, compute a subgraph $$G[V_{CK}]$$G[VCK] of $$G$$G with exactly one vertex from each partite set and the maximum number of edges or the maximum total edge weight, if $$G$$G is edge-weighted (among all such subgraphs). CK is a new problem motivated by several applications and no existing algorithm directly solves it. In this paper, we first show that CK is NP-hard even if $$\lambda =2$$?=2, and cannot be approximated within a factor of $$16/17$$16/17 unless P = NP. Then, we present a random-sampling-based PTAS for dense CK. As its application, we show that CK can be used to determine the pattern of chromosome associations in the nucleus for a population of cells. We test our approach by using random and real biological data; experimental results suggest that our approach yields near optimal solutions, and significantly outperforms existing approaches.

In this paper, we use the connection between dynamic monopolies and feedback vertex sets to establish explicit formulas and new bounds for decycling number $$\nabla (G)$$?(G) when $$G$$G is one of the following classes of graphs: cycle permutation graphs, generalized Petersen graphs, and torus cordalis. In the first part of this paper, we show that if $$G$$G is a cycle permutation graph or a generalized Petersen graph on $$2n$$2n vertices, then $$\nabla (G)=\lceil (n+1)/2\rceil $$?(G)=?(n+1)/2?. These results extend a recent result by Zaker (Discret Math 312:1136---1143, 2012) and partially answer a question of Bau and Beineke (Australas J Comb 25:285---298, 2002). Note that our definition of a generalized Petersen graph is more general than the one used in Zaker (Discret Math 312:1136---1143, 2012). The second and major part of this paper is devoted to proving new upper bounds and exact values on the size of the minimum feedback vertex set and minimum dynamic monopoly for torus cordalis. Our results improve the previous results by Flocchini in 2004.

We initiate the study of relaxed $$L(2,1)$$L(2,1)-labelings of graphs. Suppose $$G$$G is a graph. Let $$u$$u be a vertex of $$G$$G. A vertex $$v$$v is called an $$i$$i-neighbor of $$u$$u if $$d_G(u,v)=i$$dG(u,v)=i. A $$1$$1-neighbor of $$u$$u is simply called a neighbor of $$u$$u. Let $$s$$s and $$t$$t be two nonnegative integers. Suppose $$f$$f is an assignment of nonnegative integers to the vertices of $$G$$G. If the following three conditions are satisfied, then $$f$$f is called an $$(s,t)$$(s,t)-relaxed $$L(2,1)$$L(2,1)-labeling of $$G$$G: (1) for any two adjacent vertices $$u$$u and $$v$$v of $$G, f(u)\not =f(v)$$G,f(u)?f(v); (2) for any vertex $$u$$u of $$G$$G, there are at most $$s$$s neighbors of $$u$$u receiving labels from $$\{f(u)-1,f(u)+1\}$${f(u)-1,f(u)+1}; (3) for any vertex $$u$$u of $$G$$G, the number of $$2$$2-neighbors of $$u$$u assigned the label $$f(u)$$f(u) is at most $$t$$t. The minimum span of $$(s,t)$$(s,t)-relaxed $$L(2,1)$$L(2,1)-labelings of $$G$$G is called the $$(s,t)$$(s,t)-relaxed $$L(2,1)$$L(2,1)-labeling number of $$G$$G, denoted by $$\lambda ^{s,t}_{2,1}(G)$$?2,1s,t(G). It is clear that $$\lambda ^{0,0}_{2,1}(G)$$?2,10,0(G) is the so called $$L(2,1)$$L(2,1)-labeling number of $$G$$G. $$\lambda ^{1,0}_{2,1}(G)$$?2,11,0(G) is simply written as $$\widetilde{\lambda }(G)$$?~(G). This paper discusses basic properties of $$(s,t)$$(s,t)-relaxed $$L(2,1)$$L(2,1)-labeling numbers of graphs. For any two nonnegative integers $$s$$s and $$t$$t, the exact values of $$(s,t)$$(s,t)-relaxed $$L(2,1)$$L(2,1)-labeling numbers of paths, cycles and complete graphs are determined. Tight upper and lower bounds for $$(s,t)$$(s,t)-relaxed $$L(2,1)$$L(2,1)-labeling numbers of complete multipartite graphs and trees are given. The upper bounds for $$(s,1)$$(s,1)-relaxed $$L(2,1)$$L(2,1)-labeling number of general graphs are also investigated. We introduce a new graph parameter called the breaking path covering number of a graph. A breaking path $$P$$P is a vertex sequence $$v_1,v_2,\ldots ,v_k$$v1,v2,?,vk in which each $$v_i$$vi is adjacent to at least one vertex of $$v_{i-1}$$vi-1 and $$v_{i+1}$$vi+1 for $$i=2,3,\ldots ,k-1$$i=2,3,?,k-1. A breaking path covering of $$G$$G is a set of disjoint such vertex sequences that cover all vertices of $$G$$G. The breaking path covering number of $$G$$G, denoted by $$bpc(G)$$bpc(G), is the minimum number of breaking paths in a breaking path covering of $$G$$G. In this paper, it is proved that $$\widetilde{\lambda }(G)= n+bpc(G^{c})-2$$?~(G)=n+bpc(Gc)-2 if $$bpc(G^{c})\ge 2$$bpc(Gc)?2 and $$\widetilde{\lambda }(G)\le n-1$$?~(G)≤n-1 if and only if $$bpc(G^{c})=1$$bpc(Gc)=1. The breaking path covering number of a graph is proved to be computable in polynomial time. Thus, if a graph $$G$$G is of diameter two, then $$\widetilde{\lambda }(G)$$?~(G) can be determined in polynomial time. Several conjectures and problems on relaxed $$L(2,1)$$L(2,1)-labelings are also proposed.

In this paper, we prove the Hyers–Ulam stability theorem when $${f, g, h : \mathbb{R} \to \mathbb{R}}$$ satisfy $$|f(x + y) - g(x) - h(y)| \leq \epsilon$$ in a set $${\Gamma \subset \mathbb{R}^{2}}$$ of measure $${m(\Gamma) = 0}$$ , which refines a previous result in Chung (Aequat Math 83:313–320, 2012) and gives an affirmative answer to the question in the paper. As a direct consequence we obtain that if $${f, g, h : \mathbb{R} \to \mathbb{R}}$$ satisfy the Pexider equation $$f(x + y) - g(x) - h(y) = 0$$ in $${\Gamma}$$ , then the equation holds for all $${x, y \in \mathbb{R}}$$ . Using our method of construction of the set, we can find a set $${\Gamma \subset \mathbb{R}^{2n}}$$ of 2n-dimensional measure 0 and obtain the above result for the functions $${f, g, h : \mathbb{R}^{n} \to \mathbb{C}}$$ .

This paper studies co-k-plex vertex partitions and more specifically co-2-plex vertex partitions. Co-$$k$$k-plexes and $$k$$k-plexes were first introduced in 1978 in the context of social network analysis. However, the study of co-k-plex vertex partitions or decomposing a graphs into degree bounded subgraphs can be at least dated back to the work of Lovasz (Studia Sci Math Hung 1:237---238, 1966). In this paper, we derive analogues for well-known results on the chromatic number, and present two algorithms for constructing co-2-plex vertex partitions. The first algorithm minimizes the number of partition classes while the second algorithm minimizes a weighted sum of the partition classes, where the weight of a partition class depends on the level of adjacency among its vertices.

The problem of learning queries from tree structured data is studied by this paper. A tree structured data is modeled as a node-labeled tree $$T$$ T , and applying a query $$q$$ q on $$T$$ T will return a set $$q(T)$$ q ( T ) which is a subset of nodes in $$T$$ T . For a tree-node pair $$(T,t)$$ ( T , t ) where $$t$$ t is a node in $$T$$ T , $$q$$ q is called to accept the pair if $$t\in {q(T)}$$ t ? q ( T ) , and reject the pair if $$t\notin {q(T)}$$ t ? q ( T ) . For some query class $$\mathcal{L }$$ L , given tree-node pair sets $$E_p$$ E p and $$E_n$$ E n , the tree query learning problem is to find a query $$q\in \mathcal{L }$$ q ? L such that (1) $$q$$ q rejects all pairs in $$E_n$$ E n , and (2) the size of pairs in $$E_p$$ E p accepted by $$q$$ q is maximized. On four different query classes $$\mathcal Q ^{\tiny /}$$ Q / , $$\mathcal Q ^{\tiny /,*}$$ Q / , ? , $$\mathcal Q ^{\tiny /,//}$$ Q / , / / and $$\mathcal Q ^{\tiny /,[]}$$ Q / , [ ] , this paper studies the hardness of the corresponding tree query learning problems. For $$\mathcal Q ^{\tiny /}$$ Q / , a PTime algorithm is given. For $$\mathcal Q ^{\tiny /,*}$$ Q / , ? and $$\mathcal Q ^{\tiny /,//}$$ Q / , / / , the NP-complete results are shown. For $$\mathcal Q ^{\tiny /,[]}$$ Q / , [ ] , the problem is shown to be NP-hard by considering two constrained fragments of $$\mathcal Q ^{\tiny /,[]}$$ Q / , [ ] . Also, for $$\mathcal Q ^{\tiny /,*}$$ Q / , ? , $$\mathcal Q ^{\tiny /,[]}$$ Q / , [ ] and $$\mathcal Q ^{\tiny /,//}$$ Q / , / / , it is shown that there are no $$n^{1-\epsilon }$$ n 1 ? ∈ -approximation algorithms for any $$\epsilon >0$$ ∈ > 0 .

In this paper, we study the Radiation hybrid map construction ( $$\mathsf{{RHMC} }$$ ) problem which is about reconstructing a genome from a set of gene clusters. The problem is known to be $$\mathsf{{NP} }$$ -complete even when all gene clusters are of size two and the corresponding problem ( $$\mathsf{{RHMC}_2 }$$ ) admits efficient constant-factor approximation algorithms. In this paper, for the first time, we consider the more general case when the gene clusters can have size either two or three ( $$\mathsf{{RHMC}_3 }$$ ). Let $${p\text{- }\mathsf {RHMC} }$$ be a parameterized version of $$\mathsf{{RHMC} }$$ where the parameter is the size of solution. We present a linear kernel for $${p\text{- }\mathsf {RHMC}_3 }$$ of size $$22k$$ that when combined with a bounded search-tree algorithm, gives an FPT algorithm running in $$O(6^kk+n)$$ time. For $${p\text{- }\mathsf {RHMC}_3 }$$ we present a bounded search tree algorithm which runs in $$O^*(2.45^k)$$ time, greatly improving the previous bound using weak kernels.

In this paper, we initiate the study of total liar's domination of a graph. A subset L⊆V of a graph G=(V,E) is called a total liar's dominating set of G if (i) for all v?V, |N G (v)?L|?2 and (ii) for every pair u,v?V of distinct vertices, |(N G (u)?N G (v))?L|?3. The total liar's domination number of a graph G is the cardinality of a minimum total liar's dominating set of G and is denoted by ? TLR (G). The Minimum Total Liar's Domination Problem is to find a total liar's dominating set of minimum cardinality of the input graph G. Given a graph G and a positive integer k, the Total Liar's Domination Decision Problem is to check whether G has a total liar's dominating set of cardinality at most k. In this paper, we give a necessary and sufficient condition for the existence of a total liar's dominating set in a graph. We show that the Total Liar's Domination Decision Problem is NP-complete for general graphs and is NP-complete even for split graphs and hence for chordal graphs. We also propose a 2(lnΔ(G)+1)-approximation algorithm for the Minimum Total Liar's Domination Problem, where Δ(G) is the maximum degree of the input graph G. We show that Minimum Total Liar's Domination Problem cannot be approximated within a factor of $(\frac{1}{8}-\epsilon)\ln(|V|)$ for any ∈>0, unless NP⊆DTIME(|V|loglog|V|). Finally, we show that Minimum Total Liar's Domination Problem is APX-complete for graphs with bounded degree 4.

For two positive integers j and k with j?k, an L(j,k)-labeling of a graph G is an assignment of nonnegative integers to V(G) such that the difference between labels of adjacent vertices is at least j, and the difference between labels of vertices that are distance two apart is at least k. The span of an L(j,k)-labeling of a graph G is the difference between the maximum and minimum integers used by it. The L(j,k)-labelings-number of G is the minimum span over all L(j,k)-labelings of G. This paper focuses on L(2,1)-labelings-number of the edge-path-replacement G(P k ) of a graph G. Note that G(P 3) is the incidence graph of G. L(2,1)-labelings of the edge-path-replacement G(P 3) of a graph, called (2,1)-total labeling of G, was introduced by Havet and Yu in 2002 (Workshop graphs and algorithms, Dijon, France, 2003; Discrete Math. 308:498---513, 2008). They (Havet and Yu, Discrete Math. 308:498---513, 2008) obtain the bound $\Delta+1\leq\lambda^{T}_{2}(G)\leq2\Delta+1$ and conjectured $\lambda^{T}_{2}(G)\leq\Delta+3$ . In this paper, we obtain that ?(G(P k ))?Δ+2 for k?5, and conjecture ?(G(P 4))?Δ+2 for any graph G with maximum degree Δ.

In this paper, we introduce a new iterative algorithm for solving the split equality generalized mixed equilibrium problems. The weak and strong convergence theorems are proved for demi-contractive mappings in real Hilbert spaces. Several special cases are also discussed. As applications, we employ our results to get the convergence results for the split equality convex differentiable optimization problem, the split equality convex minimization problem, and the split equality mixed equilibrium problem. The results in this paper generalize, extend, and unify some recent results in the literature.

A variation of the classical channel assignment problem is to assign a radio channel which is a nonnegative integer to each radio transmitter so that "close" transmitters must receive different channels and "very close" transmitters must receive channels that are at least two channels apart. The goal is to minimize the span of a feasible assignment. This channel assignment problem can be modeled with distance-dependent graph labelings. A k-L(2,1)-labeling of a graph G is a mapping f from the vertex set of G to the set {0,1,2,?,k} such that |f(x)?f(y)|?2 if d(x,y)=1 and $f(x)\not =f(y)$ if d(x,y)=2, where d(x,y) is the distance between vertices x and y in G. The minimum k for which G admits an k-L(2,1)-labeling, denoted by ?(G), is called the ?-number of G. Very little is known about ?-numbers of 3-regular graphs. In this paper we focus on an important subclass of 3-regular graphs called generalized Petersen graphs. For an integer n?3, a graph G is called a generalized Petersen graph of order n if and only if G is a 3-regular graph consisting of two disjoint cycles (called inner and outer cycles) of length n, where each vertex of the outer (resp. inner) cycle is adjacent to exactly one vertex of the inner (resp. outer) cycle. In 2002, Georges and Mauro conjectured that ?(G)?7 for all generalized Petersen graphs G of order n?7. Later, Adams, Cass and Troxell proved that Georges and Mauro's conjecture is true for orders 7 and 8. In this paper it is shown that Georges and Mauro's conjecture is true for generalized Petersen graphs of orders 9, 10, 11 and 12.

Let k be a positive integer and let G be a graph with vertex set V(G). The total {k}-dominating function (T{k}DF) of a graph G is a function f from V(G) to the set {0,1,2,?,k}, such that for each vertex v?V(G), the sum of the values of all its neighbors assigned by f is at least k. A set {f 1,f 2,?,f d } of pairwise different T{k}DFs of G with the property that $\sum_{i=1}^{d}f_{i}(v)\leq k$ for each v?V(G), is called a total {k}-dominating family (T{k}D family) of G. The total {k}-domatic number of a graph G, denoted by $d_{t}^{\{k\}}(G)$ , is the maximum number of functions in a T{k}D family. In this paper, we determine the exact values of the total {k}-domatic numbers of wheels and complete graphs, which answers an open problem of Sheikholeslami and Volkmann (J. Comb. Optim., 2010) and completes a result in the same paper.

Latency of information propagating in wireless network is gaining more and more attention recently. This paper studies the problem of t-Latency Bounded Information Propagation (t-LBIP) problem in wireless networks which are represented by unit-disk graphs. So far, no guaranteed approximation algorithm has been achieved for t-LBIP when t?2. In this paper, we propose a Polynomial Time Approximation Scheme for t-LBIP under the condition that the maximum degree is bounded by a constant.

This paper considers the NP-hard graph problem of determining a maximum cardinality subset of vertices inducing a k-regular subgraph. For any graph G, this maximum will be denoted by ? k (G). From a well known Motzkin-Straus result, a relationship is deduced between ? k (G) and the independence number ?(G). Next, it is proved that the upper bounds ? k (G) introduced in Cardoso et al. (J. Comb. Optim., 14, 455---463, 2007) can easily be computed from ? 0(G), for any positive integer k. This relationship also allows one to present an alternative proof of the Hoffman bound extension introduced in the above paper. The paper continues with the introduction of a new upper bound on ? k (G) improving ? k (G). Due to the difficulty of computing this improved bound, two methods are provided for approximating it. Finally, some computational experiments which were performed to compare all bounds studied are reported.

An instance of the popular matching problem (POP-M) consists of a set of applicants and a set of posts. Each applicant has a preference list that strictly ranks a subset of the posts. A matching M of applicants to posts is popular if there is no other matching M? such that more applicants prefer M? to M than prefer M to M?. Abraham et al. (SIAM J. Comput. 37:1030---1045, 2007) described a linear time algorithm to determine whether a popular matching exists for a given instance of POP-M, and if so to find a largest such matching. A number of variants and extensions of POP-M have recently been studied. This paper provides a characterization of the set of popular matchings for an arbitrary POP-M instance in terms of a structure called the switching graph, a directed graph computable in linear time from the preference lists. We show that the switching graph can be exploited to yield efficient algorithms for a range of associated problems, including the counting and enumeration of the set of popular matchings, generation of a popular matching uniformly at random, finding all applicant-post pairs that can occur in a popular matching, and computing popular matchings that satisfy various additional optimality criteria. Our algorithms for computing such optimal popular matchings improve those described in a recent paper by Kavitha and Nasre (Proceedings of MATCH-UP: Matching Under Preferences--Algorithms and Complexity, 2008).

Let $$f : {\mathbb{R}} \longrightarrow {\mathbb{R}}$$ denote the function given by $$f(t) = \sum \limits^{\infty}_{n=0} a_{n}t^{n}, t \in {\mathbb{R}}$$ , where $$a_n \geq 0, n \in {\mathbb{N}}$$ . Let K be a closed convex cone in a real Banach space and $$H : K \longrightarrow cc(K)$$ a linear and continuous set-valued function with nonempty, convex and compact values in K. The set-valued function $$F^t(x) := \sum \limits_{n=0}^{\infty} a_{n}t^{n}H^{n}(x), x \in K$$ is linear and continuous for all $$t \geq 0$$ and $$F^{t} \circ F^{s}(x) \subseteq \sum \limits_{n=0}^{\infty} c_{n}H^{n} (x), x \in K$$ where $$c_{n} = \sum \limits_{k=0}^{n} a_{k} a_{n-k}{{t^{k}}s^{n-k}}, t, s \geq 0$$ . The paper generalizes papers of J. Plewnia and M. Piszczek where f is an exponential and a cosine function respectively.

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph G with no isolated vertex is a dominating set S of vertices whose induced subgraph has a perfect matching. The set S is called a differentiating-paired dominating set if for every pair of distinct vertices u and v in V(G), N[u]∩S≠N[v]∩S, where N[u] denotes the set consisting of u and all vertices adjacent to u. In this paper, we provide a constructive characterization of trees that do not have a differentiating-paired dominating set.

It is well known that there are no nonzero linear derivations on complex commutative semisimple Banach algebras. In this paper we prove the following extension of this result. Let A be a complex semisimple Banach algebra and let D : A → A be a linear mapping satisfying the relation D(x 2) = 2xD(x) for all x ∈ R. In this case D = 0. Throughout, R will represent an associative ring with center Z(R). A ring R is n-torsion free, where n > 1 is an integer, if nx = 0, x ∈ R implies x = 0. As usual the commutator xy − yx will be denoted by [x, y]. We shall use the commutator identities [xy, z] = [x, z] y + x [y, z] and [x, yz] = [x, y] z + y [x, z] for all x, y, z ∈ R. Recall that a ring R is prime if for a, b ∈ R, aRb = (0) implies that either a = 0 or b = 0, and is semiprime in case aRa = (0) implies that a = 0. An additive mapping D is called a derivation if D(xy) = D(x)y + xD(y) holds for all pairs x, y ∈ R, and is called a Jordan derivation in case D(x 2) = D(x)x + xD(x) is fulfilled for all x ∈ R. Obviously, any derivation is a Jordan derivation. The converse is in general not true. Herstein ([8]) has proved that any Jordan derivation on a 2-torsion free prime ring is a derivation (see also [1]). Cusack ([5]) has generalized Herstein’s result to 2-torsion free semiprime rings (see [2] for an alternative proof). An additive mapping D : R → R is called a left derivation if D(xy) = yD(x) + xD(y) holds for all pairs x, y ∈ R and is called a left Jordan derivation (or Jordan left derivation) in case D(x 2) = 2xD(x) is fulfilled for all x ∈ R. In this paper by a Banach algebra we mean a Banach algebra over the complex field.

The object of this paper is to investigate possibilities of extending the solution F : C → W of certain functional equations to V and of n-Jensen functions f : Cn → W to Vn, where C is a \({\mathbb{Q}}\) -convex subset of V and V, W are \({\mathbb{Q}}\) -vector spaces. Solutions of the considered functional equations defined on V and n-Jensen functions defined on Vn have been utilized in recent papers (e.g. [2], [4]) in order to characterize generalized polynomials P : V →W of degree ≤ n. Therefore these extension theorems may present a point of view for defining generalized polynomials on a \({\mathbb{Q}}\) -convex subset of a \({\mathbb{Q}}\) -vector space.

In the paper “On logarithmic convexity for power sums and related results” (2008), we introduced means by using power sums and increasing function. In this paper, we will define new means of convex type in connection to power sums. Also we give integral analogs of new means.

A real-valued function f defined on an open convex set $$D\subseteq X $$ is called (d, t)-convex if it satisfies $$f(tx + (1 - t)y)\leq tf(x)+(1 - t)f(y) + d(x, y)$$ for all $$x,\, y \in D$$ , where $$d : X {\times} X \rightarrow{\mathbb{R}}$$ is a given function and t $$\in$$ ]0, 1[ is a fixed parameter. The main result of the paper states that if f is locally bounded from above at a point of D and (d, t)-convex then it satisfies the convexity-type inequality (under some assumptions) $$f(sx + (1 - s)y)\leq sf(x) + (1 - s)f(y) +\varphi(s)d(x, y)$$ for all $$x, y \in D$$ and s $$\in$$ [0, 1], where $$\varphi : [0, 1] \rightarrow {\mathbb{R}}$$ is defined as the fixed point of a certain contraction. The main result of this paper offers a generalization of the celebrated Bernstein and Doetsch theorem and the recent results by Nikodem and Ng, Pales and the author.

In a series of 2 papers, Kang, Du and Tian solved the existence problem for G-decomposition of λKn when G is any simple graph with 6 vertices and 7 edges, except when G is the graph T=K4∪K2. Notice that a T-decomposition can be considered to be a Pairwise Balanced Design in which each block of size 4 has been matched to a block of size 2. In this paper we remove this exception for all λ≥2. The case when λ=1 is also addressed.

Very recently, in a series of subsequent papers, Nan and Charoensawan introduced the notion of g-coincidence point of two mappings in different settings (metric spaces and G-metric spaces) and proved some theorems in order to guarantee the existence and uniqueness of such kind of points. Although their notion seems to be attractive, in this paper, we show how this concept can be reduced to the unidimensional notion of coincidence point, and how their main theorems can be seen as particular cases of existing results. Moreover, we prove that the proofs of their main statements have some gaps.

In this paper, an iterative algorithm is introduced to solve the split common fixed point problem for asymptotically nonexpansive mappings in Hilbert spaces. The iterative algorithm presented in this paper is shown to possess strong convergence for the split common fixed point problem of asymptotically nonexpansive mappings although the mappings do not have semi-compactness. Our results improve and develop previous methods for solving the split common fixed point problem.

In this paper, we consider the problem of enumerating all maximal motifs in an input string for the class of repeated motifs with wild cards. A maximal motif is such a representative motif that is not properly contained in any larger motifs with the same location lists. Although the enumeration problem for maximal motifs with wild cards has been studied in Parida et al. (2001), Pisanti et al. (2003) and Pelfrene et al. (2003), its output-polynomial time computability has been still open. The main result of this paper is a polynomial space polynomial delay algorithm for the maximal motif enumeration problem for the repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length n in O(n3) time per motif with O(n) space, in particular O(n3) delay. The key of the algorithm is depth-first search on a tree-shaped search route over all maximal motifs based on a technique called prefix-preserving closure extension. We also show an exponential lower bound and a succinctness result on the number of maximal motifs, which indicate the limit of a straightforward approach. The results of the computational experiments show that our algorithm can be applicable to huge string data such as genome data in practice, and does not take large additional computational cost compared to usual frequent motif mining algorithms.

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (1998) Networks 32: 199–206. A paired-dominating set of a graph G 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 $$\gamma_{\rm pr}(G)$$ , is the minimum cardinality of a paired-dominating set of G. Let G be a connected graph of order n with minimum degree at least two. Haynes and Slater (1998) Networks 32: 199–206, showed that if n ≥ 6, then $$\gamma_{\rm pr}(G) \le 2n/3$$ . In this paper, we show that there are exactly ten graphs that achieve equality in this bound. For n ≥ 14, we show that $$\gamma_{\rm pr}(G) \le 2(n-1)/3$$ and we characterize the (infinite family of) graphs that achieve equality in this bound.

This paper considers the Cardinality Constrained Quadratic Knapsack Problem (QKP) and the Quadratic Selective Travelling Salesman Problem (QSTSP). The QKP is a generalization of the Knapsack Problem and the QSTSP is a generalization of the Travelling Salesman Problem. Thus, both problems are NP hard. The QSTSP and the QKP can be solved using branch-and-cut methods. Good bounds can be obtained if strong constraints are used. Hence it is important to identify strong or even facet-defining constraints. This paper studies the polyhedral combinatorics of the QSTSP and the QKP, i.e. amongst others we identify facet-defining constraints for the QSTSP and the QKP, and provide mathematical proofs that they do indeed define facets.

In this paper we consider the problem of partitioning complete multipartite graphs with edges colored by 2 colors into the minimum number of vertex disjoint monochromatic cycles, paths and trees, respectively. For general graphs we simply address the decision version of these three problems the 2-PGMC, 2-PGMP and 2-PGMT problems, respectively. We show that both 2-PGMC and 2-PGMP problems are NP-complete for complete multipartite graphs and the 2-PGMT problem is NP-complete for bipartite graphs. This also implies that all these three problems are NP-complete for general graphs, which solves a question proposed by the authors in a previous paper. Nevertheless, we show that the 2-PGMT problem can be solved in polynomial time for complete multipartite graphs.

In 1941 S. N. Bernstein proved the following characterization theorem. Let ξ1 and ξ2 be independent random variables. If ξ1 + ξ2 and ξ1 - ξ2 are independent, then ξ1 and ξ2 are Gaussian with equal dispersion. This paper is devoted to a group analogue of the Bernstein theorem. Let X be a locally compact separable abelian group and ξ1, ξ2 be independent random X-valued variables with distributions μ1, μ2. Denote by $$ \user1{\mathbb{T}} $$ and by ∑ a the group of rotations of the circle and the a-adic solenoid, respectively. In this paper we solve the following problem: In the case where either $$ X = \user1{\mathbb{R}} \times \user1{\mathbb{T}} $$ or X = ∑ a we describe all possible distributions μ1 and μ2 under the assumption that ξ1 + ξ2 and ξ1 - ξ2 are independent.

The purpose of this paper is to study non-L 0 -linear perturbations of random isometries in random normed modules. Let (� , F, P) be a probability space, K the scalar field R of real numbers or C of complex numbers, L 0 (F, K) the equivalence classes of K-valued F-measurable random variables on � ,( E1, �·� 1 )a nd (E2, �·� 2) random normed modules over K with base (� , F, P). In this paper, we first establish the Mazur-Ulam theorem in random normed modules. Making use of this theorem and the relations between random normed modules and classical normed spaces, we show that if f : E1 → E2 is a surjective random e-isometry with f (0) = 0 and has the local property, where e ∈ L 0 (F, R )a nde ≥ 0, then there is a surjective L 0 -linear random isometry U : E1 → E2 such thatf (x )- U(x)� 2 ≤ 4e ,f or allx ∈ E1 .W e do not obtain a sharp estimate as the classical result, since random normed modules have a complicated stratification structure, which is the essential difference between random normed modules and classical normed spaces. MSC: 46A22; 46A25; 46H25

The purpose of this paper is to introduce and study a class of new general systems of set-valued variational inclusions involving relative -maximal monotone operators in Hilbert spaces. By using the generalized resolvent operator technique associated with relative -maximal monotone operators, we also construct some new iterative algorithms for finding approximation solutions to the general systems of set-valued variational inclusions and prove the convergence of the sequences generated by the algorithms. The results presented in this paper improve and extend some known results in the literature.

In this paper we consider families of rational maps of degree 2n on the Riemann sphereF λ: $$F_\lambda :\bar {\mathbb{C}} \to \bar {\mathbb{C}}$$ given by $$F_\lambda (z) = z^n + \frac{\lambda }{{z^n }}$$ where $$\lambda \in \mathbb{C} - \{ 0\} $$ andn>-2. One of our goals in this paper is to describe a type of structure that we call aCantor necklace that occurs in both the dynamical and the parameter plance forF λ. Roughly speaking, such a set is homeomorphic to a set constructed as follows. Start with the Cantor middle thirds set embedded on thex-axis in the plane. Then replace each removed open interval with an open circular disk whose diameter is the same as the length of the removed interval. A Cantor necklace is a set that is homeomorphic to the resulting union of the Cantor set and the adjoined open disks. The second goal of this paper is to use the Cantor necklaces in the parameter plane to prove the existence of several new types of Sierpinski curve Julia sets that arise in these families of rational maps. Unlike most examples of this type of Julia set, the maps on these Julia sets are structurally unstable. That is, small changes in the parameter λ give rise to Julia sets on which the dynamical behavior is quite different. In addition, we also describe a new type of related Julia set which we call a hybrid Sierpinski curve.

This paper studies the following variations of arboricity of graphs. The vertex (respectively, tree) arboricity of a graph G is the minimum number va(G) (respectively, ta(G)) of subsets into which the vertices of G can be partitioned so that each subset induces a forest (respectively, tree). This paper studies the vertex and the tree arboricities on various classes of graphs for exact values, algorithms, bounds, hamiltonicity and NP-completeness. The graphs investigated in this paper include block-cactus graphs, series-parallel graphs, cographs and planar graphs.