Liar’s domination in graphs

Assume that each vertex of a graph G is the possible location for an “intruder” such as a thief, or a saboteur, a fire in a facility or some possible processor fault in a computer network. A device at a vertex v is assumed to be able to detect the intruder at any vertex in its closed neighborhood N[v]and to identify at which vertex inN[v] the intruder is located. One must then have a dominating set S⊆V(G), a set with ∪_v∈SN[v]=V(G), to be able to identify any intruder’s location. If any one device can fail to detect the intruder, then one needs a double-dominating set. This paper considers liar’s dominating sets, sets that can identify an intruder’s location even when any one device in the neighborhood of the intruder vertex can lie, that is, any one device in the neighborhood of the intruder vertex can misidentify any vertex in its closed neighborhood as the intruder location. Liar’s dominating sets lie between double dominating sets and triple dominating sets because every triple dominating set is a liar’s dominating set, and every liar’s dominating set must double dominate.     

Geometrical extensions of Wythoff’s game

In 1905 Bouton gave the complete theory of a two-player combinatorial game: the game of Nim. Two years later, Wythoff defined his game as “a modification” of the game of Nim. In this paper, we give the sets of the losing positions of geometrical extensions of Wythoff’s game, where allowed moves are considered according to a set of vectors (v₁,…,v_n). When n=3, we present algorithms and algebraic characterizations to determine the losing positions of such games. In the last part, we investigate a bounded version of Wythoff’s game, and give a polynomial way to decide whether a game position is losing or not.     

Hamiltonicity of 6-connected line graphs

Let G be a graph and let D₆(G)={v∈V(G)|d_G(v)=6}. In this paper we prove that: (i) If G is a 6-connected claw-free graph and if |D₆(G)|≤74 or G[D₆(G)] contains at most 8 vertex disjoint K₄’s, then G is Hamiltonian; (ii) If G is a 6-connected line graph and if |D₆(G)|≤54 or G[D₆(G)] contains at most 5 vertex disjoint K₄’s, then G is Hamilton-connected.     

The fine triangle intersections for maximum kite packings

In this paper, the fine triangle intersection problem for a pair of maximum kite packings is investigated. Let Fin(v) = {(s,t) : a pair of maximum kite packings of order v intersecting in s blocks and s+t triangles}. Let Adm(v) = {(s, t) : s + t ≤ bv , s,t are non-negative integers}, where b v = v(v 1)/8 . It is established that Fin(v) = Adm(v)\{(bv-1, 0), (bv-1,1)} for any integer v ≡ 0, 1 (mod 8) and v ≥ 8; Fin(v) = Adm(v) for any integer v ≡ 2, 3, 4, 5, 6, 7 (mod 8) and v ≥ 4.     

Characterization and representation problems for intersection betweennesses

For a set system M=(M_v)_v∈V indexed by the elements of a finite set V, the intersection betweenness B(M) induced by M consists of all triples (u,v,w)∈V³ with M_u∩M_w⊆M_v. Similarly, the strict intersection betweenness B_s(M) induced by M consists of all triples (u,v,w)∈B(M) such that u, v, and w are pairwise distinct. The notion of a strict intersection betweenness was introduced by Burigana [L. Burigana, Tree representations of betweenness relations defined by intersection and inclusion, Math. Soc. Sci. 185 (2009) 5-36]. We provide axiomatic characterizations of intersection betweennesses and strict intersection betweennesses. Our results yield a simple and efficient algorithm that constructs a representing set system for a given (strict) intersection betweenness. We study graphs whose strict shortest path betweenness is a strict intersection betweenness. Finally, we explain how the algorithmic problem related to Burigana’s notion of a partial tree representation can be solved efficiently using well-known algorithms.     

*-Generalized polynomial identities of finite dimensional central simple algebras

LetD be a finite dimensional central simple algebra with involution * of the first kind. We prove (in a fixed number of variables) the ideal of *-GPI’s ofD is generated by a finite collection of elements of the form [v _ij ,v _pq ] andv _ij ?v _ij ^* where thev _ij ’s are first degree generalized polynomials.     

Halving Steiner 2-designs

A Steiner 2-design S(2,k,v) is said to be halvable if the block set can be partitioned into two isomorphic sets. This is equivalent to an edge-disjoint decomposition of a self-complementary graph G on v vertices into K_ks. The obvious necessary condition of those orders v for which there exists a halvable S(2,k,v) is that v admits the existence of an S(2,k,v) with an even number of blocks. In this paper, we give an asymptotic solution for various block sizes. We prove that for any k?5 or any Mersenne prime k, there is a constant number v₀ such that if v>v₀ and v satisfies the above necessary condition, then there exists a halvable S(2,k,v). We also show that a halvable S(2,2ⁿ,v) exists for over a half of possible orders. Some recursive constructions generating infinitely many new halvable Steiner 2-designs are also presented.     

On the optimality of a class of designs with three concurrences

In the present paper we consider a class of unequally replicated designs having concurrence range 2 and spectrum of the form μ₁(μ₂)^v−3μ₃. Now, Jacroux’s [Some sufficient conditions for the type I optimality of block designs, J. Statist. Plann. Inference 11 (1985) 385-396] Proposition 2.4 says that a design with spectrum of the above form, if satisfies some further conditions, is type 1 optimal. Unfortunately, this proposition does not apply to our designs since they have a poor status regarding E-optimality. Yet we are able to prove the A-optimality (in the general class) of these designs using majorisation technique. A method of construction of an infinite series of our A-optimal designs has also been given.The first and only known infinite series of examples of designs satisfying Jacroux’s conditions appears to be the first one in Section 4.1 of Morgan and Srivastav [On the Type-1 optimality of nearly balanced incomplete block designs with small concurrence range, Statist. Sinica 10 (2000) 1091-1116] - hitherto referred to as [MS]. In this paper, we use majorisation technique to prove stronger optimality properties of the above mentioned designs of [MS] as well as to present simpler proof of another optimality result in [MS].     

Nonisomorphic Maximum Packing and Minimum Covering of K v with 8-Cycles

The maximum packing C ₈-max PD(v) and minimum covering C ₈-minCD(v) of K _v with 8-cycles are studied, all structures with the nonisomorphic leave (excess) are presented. In Li et al. (Graphs Combin 25:735–752, 2009), C ₈-max PD(v) and C ₈-minCD(v) have been determined for odd v. In this paper, we introduce the enumeration of nonisomorphic ${(v,\frac{v}{2}+s)}$ -graphs (s = 4, 6), give complete solution of the maximum packing and minimum covering designs of K _v with 8-cycles for any even v with all possible leaves (excesses).     

Functional equations for vector products and quaternions

In our paper we find all functions ${f : \mathbb {R} \times \mathbb {R}^{3} \rightarrow \mathbb {H}}$ and ${g : \mathbb {R}^{3} \rightarrow \mathbb {H}}$ satisfying ${f (r, {\bf v}) f (s, {\bf w}) = -\langle{\bf v},{\bf w}\rangle + f (rs, s{\bf v} + r{\bf w} + {\bf v} \times {\bf w})}$ ${(r, s \in \mathbb {R}, {\bf v},{\bf w} \in \mathbb {R}^{3})}$ , and ${g({\bf v})g({\bf w}) = -\langle{\bf v}, {\bf w}\rangle + g({\bf v} \times {\bf w})}$ $({{\bf v},{\bf w} \in \mathbb {R}^{3}})$ . These functional equations were motivated by the well-known identities for vector products and quaternions, which can be obtained from the solutions f (r, (v ₁, v ₂, v ₃)) = r + v ₁ i + v ₂ j + v ₃ k and g((v ₁ ,v ₂, v ₃)) = v ₁ i + v ₂ j + v ₃ k.     

On Hu-subgroups and anti fuzzy Hu-subgroups

In this paper we define the concept of anti fuzzyH _v-subgroup of anH _v-group, and prove a few theorems concerning this concept. We also obtain a necessary and sufficient condition for a fuzzy subset of anH _v-group to be an anti fuzzyH _v-subgroup. We also abtain a relation between the fuzzyH _v-subgroups and the anti fuzzyH _v-subgroups.     

Inventory models for perishable items with inventory level dependent demand rate

This paper presents inventory models for perishable items with inventory level dependent demand rate. The models with and without backlogging are studied. In the backlogging model, it is assumed that the backlogging rate is dependent on the waiting time and the amount of products already backlogged simultaneously. Two cases that holding inventory is profitable or not are studied, respectively. The smallest shelf space to ensure shortage not occur when holding inventory is not profitable is obtained. In the model without backlogging, it is assumed that the remaining stock at the end of the inventory cycle is disposed of with salvage value. The necessary and sufficient conditions for the existence and uniqueness of the optimal solution of these models are investigated. At last, some numerical examples are presented to illustrate the effectiveness of the proposed model. The model in this paper is generalization of present ones. In particularly, the model is reduced to Padmanabhan and Vrat’s when δ₁ = 0, and Dye and Ouyang’s when δ₂ = 0. If S = s and δ₂ = 0, it is Chang, Goyal and Teng’s model.     

Alternating eulerian trails with prescribed degrees in two edge-colored complete graphs

Let K_n be the complete graph with vertex set {v₁, v₂, …, v_n} and let g=(g₁, …, g_n) be a sequence of positive integers. Color each edge of this K_n red or blue. In this paper necessary and sufficient conditions are given which guarantee the existence of a connected spanning subgraph F in K_n (as colored) with both red degree and blue degree in F at vertex v₁ equal to g_i. When each g_i = 1 this answers a question of Erdös proved in this special case in [1].     

A note on the sequence spacel (p v )

In this paper, the linear isometry of the sequence space l(p_v) into itself is specified as the automorphism of l(p_v) onto itself, when (p_v) satisfies the conditions, (i) 0 < p_v? 1, (ii) 1 +d ? p_v ? p < ∞,q < q_v < 1+d/d,d > o When (p_v) satisfies condition (ii),l (p_v) andl (q_v) are proved to be perfect spaces in the sense of Kothe and Toeplitz. A similar result connecting linear isometry and automorphism has been noted in the case of a non-normable complete linear metric space whose conjugate space is also determined.     

A kind of multiquadric quasi-interpolation operator satisfying any degree polynomial reproduction property to scattered data

In this paper, by virtue of using the linear combinations of the shifts of f(x) to approximate the derivatives of f(x) and Waldron’s superposition idea (2009), we modify a multiquadric quasi-interpolation with the property of linear reproducing to scattered data on one-dimensional space, such that a kind of quasi-interpolation operator L_r+1f has the property of r+1(r∈Z,r≥0) degree polynomial reproducing and converges up to a rate of r+2. There is no demand for the derivatives of f in the proposed quasi-interpolation L_r+1f, so it does not increase the orders of smoothness of f. Finally, some numerical experiments are shown to compare the approximation capacity of our quasi-interpolation operators with that of Wu-Schaback’s quasi-interpolation scheme and Feng-Li’s quasi-interpolation scheme.     

Broadcasting secure messages via optimal independent spanning trees in folded hypercubes

Fault-tolerant broadcasting and secure message distribution are important issues for network applications. It is a common idea to design multiple spanning trees with a specific property in the underlying graph of a network to serve as a broadcasting scheme or a distribution protocol for receiving high levels of fault-tolerance and security. An n-dimensional folded hypercube, denoted by FQ_n, is a strengthening variation of hypercube by adding additional links between nodes that have the furthest Hamming distance. In, [12], Ho(1990) proposed an algorithm for constructing n+1 edge-disjoint spanning trees each with a height twice the diameter of FQ_n. Yang et al. (2009), [29] recently proved that Ho’s spanning trees are indeed independent, i.e., any two spanning trees have the same root, say r, and for any other node v≠r, the two different paths from v to r, one path in each tree, are internally node-disjoint. In this paper, we provide another construction scheme to produce n+1 independent spanning trees of FQ_n, where the height of each tree is equal to the diameter of FQ_n plus one. As a result, the heights of independent spanning trees constructed in this paper are shown to be optimal.     

Equity-linked pension schemes with guarantees

This paper analyses the relationship between the level of a return guarantee in an equity-linked pension scheme and the proportion of an investor’s contribution needed to finance this guarantee. Three types of schemes are considered: investment guarantee, contribution guarantee and surplus participation. The evaluation of each scheme involves pricing an Asian option, for which relatively tight upper and lower bounds can be calculated in a numerically efficient manner.We find a negative (and for two contract specifications also concave) relationship between the participation in the surplus return of the investment strategy and the guarantee level in terms of a minimum rate of return. Furthermore, the introduction of the possibility of early termination of the contract (e.g. due to the death of the investor) has no qualitative and very little quantitative impact on this relationship.     

A new class for large sets of almost Hamilton cycle decompositions

A k-cycle system of order v with index λ, denoted by CS(v, k, λ), is a collection A of k-cycles (blocks) of K _v such that each edge in K _v appears in exactly λ blocks of A. A large set of CS(v, k, λ)s is a partition of the set of all k-cycles of K _v into CS(v, k, λ)_s, and is denoted by LCS(v, k, λ). A (v ?1)-cycle in K _v is called almost Hamilton. The completion of the existence problem for LCS(v, v?1, λ) depends only on one case: all v ≥ 4 for λ = 2. In this paper, it is shown that there exists an LCS(v, v ? 1, 2) for all v ≡ 2 (mod 4), v ≥ 6.     

Hall number for list colorings of graphs: Extremal results

Given a graph G=(V,E) and sets L(v) of allowed colors for each v∈V, a list coloring of G is an assignment of colors φ(v) to the vertices, such that φ(v)∈L(v) for all v∈V and φ(u)≠φ(v) for all uv∈E. The choice number of G is the smallest natural number k admitting a list coloring for G whenever |L(v)|≥k holds for every vertex v. This concept has an interesting variant, called Hall number, where an obvious necessary condition for colorability is put as a restriction on the lists L(v). (On complete graphs, this condition is equivalent to the well-known one in Hall’s Marriage Theorem.) We prove that vertex deletion or edge insertion in a graph of order n>3 may make the Hall number decrease by as much as n−3. This estimate is tight for all n. Tightness is deduced from the upper bound that every graph of order n has Hall number at most n−2. We also characterize the cases of equality; for n≥6 these are precisely the graphs whose complements are K₂∪(n−2)K₁, P₄∪(n−4)K₁, and C₅∪(n−5)K₁. Our results completely solve a problem raised by Hilton, Johnson and Wantland [A.J.W. Hilton, P.D. Johnson, Jr., E. B. Wantland, The Hall number of a simple graph, Congr. Numer. 121 (1996), 161-182, Problem 7] in terms of the number of vertices, and strongly improve some estimates due to Hilton and Johnson [A.J.W. Hilton, P.D. Johnson, Jr., The Hall number, the Hall index, and the total Hall number of a graph, Discrete Appl. Math. 94 (1999), 227-245] as a function of maximum degree.     

New Effects of an Old Z. Zalcwasser's Theorem

It is well known that the strong (C, 1)-summability of an orthogonal series does not imply its very strong (C, 1)-summability, generally. For a given index-sequence {v _n }, first, Z. Zalcwasser gave an interesting condition implying the strong (C, 1)-summability of these partial sums s _{v n} (x). We show that Zalcwasser's condition on {v _n } holds if and only if the subsequence {v ₂ n} is quasi geometrically increasing. Utilizing this fact and known theorems several strong summability results are presented for given index-sequences {v _n }.