Axiomatics for fuzzy rough sets

A fuzzy T-rough set consists of a set X and a T-similarity relation R on X, where T is a lower semi-continuous triangular norm. We generalize the Farinas-Prade definition for the upper approximation operator of a fuzzy T-rough set (X, R); given originally for the special case T = Min, to the case of arbitrary T. We propose a new definition for the lower approximation operator of (X,R). Our definition satisfies the two important identities and , as well as a number of other interesting properties. We provide axiomatics to fully characterize those upper and lower approximations.     

Zagreb indices of graphs

The first Zagreb index M₁(G) is equal to the sum of squares of the degrees of the vertices, and the second Zagreb index M₂(G) is equal to the sum of the products of the degrees of pairs of adjacent vertices of the underlying molecular graph G. In this paper, we obtain lower and upper bounds on the first Zagreb index M₁(G) of G in terms of the number of vertices (n), number of edges (m), maximum vertex degree (Δ), and minimum vertex degree (δ). Using this result, we find lower and upper bounds on M₂(G). Also, we present lower and upper bounds on M₂(G) +M₂(G) in terms of n, m, Δ, and δ, where G denotes the complement of G. Moreover, we determine the bounds on first Zagreb coindex M₁(G) and second Zagreb coindex M₂(G). Finally, we give a relation between the first Zagreb index and the second Zagreb index of graph G.     

Parallel searching on m rays

We investigate parallel searching on m concurrent rays. We assume that a target t is located somewhere on one of the rays; we are given a group of m point robots each of which has to reach t. Furthermore, we assume that the robots have no way of communicating over distance. Given a strategy S we are interested in the competitive ratio defined as the ratio of the time needed by the robots to reach t using S and the time needed to reach t if the location of t is known in advance.

If a lower bound on the distance to the target is known, then there is a simple strategy which achieves a competitive ratio of 9—independent of m. We show that 9 is a lower bound on the competitive ratio for two large classes of strategies if m2.

If the minimum distance to the target is not known in advance, we show a lower bound on the competitive ratio of 1+2(k+1)^k+1/k^k where k=logm where log is used to denote the base-2 logarithm. We also give a strategy that obtains this ratio.     

Lower bounds of the Laplacian spectrum of graphs based on diameter

Let G be a connected graph of order n. The diameter of G is the maximum distance between any two vertices of G. In the paper, we will give some lower bounds for the algebraic connectivity and the Laplacian spectral radius of G in terms of the diameter of G.     

Principal subpermanents of the Laplacian matrix

The subdeterminants of the Laplacian matrix L(G) assigned to a graph G have a well-known combinatorial meaning. In the present paper principal subpermanents per L_K(G) and coefficients p_k(G) of the permanental characteristic polynomial of L(G) are expressed by means of some collections of subgraphs of G. This expansion is used to obtain lower bounds for perL(G),per L_K(G) and p_k(G).     

On L(d,1)-labelings of graphs

Given a graph G and a positive integer d, an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)−f(v)|d; if u and v are not adjacent but there is a two-edge path between them, then |f(u)−f(v)|1. The L(d,1)-number of G, λ_d(G), is defined as the minimum m such that there is an L(d,1)-labeling f of G with f(V){0,1,2,…,m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ_d(G)Δ²+(d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ_d(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs.     

Curves with degenerate general hypersurface sections

Let YPⁿ be a non-degenerate curve such that for a general degree t hypersurface S of Pⁿ, t2, the scheme Y∩S does not span Pⁿ. Here we give a lower bound for n in terms of t and some invariants of Y.     

Elasticity of factorizations in integral domains

For an atomic integral domain R, define(R)=sup{mn|x₁x_m=y₁y_n, each x_i,y_jεR is irreducible}. We investigate (R), with emphasis for Krull domains R. When R is a Krull domain, we determine lower and upper bounds for (R); in particular,(R)≤max{|Cl(R)| 2, 1}. Moreover, we show that for any real numbers r≥1 or R=∞, there is a Dedekind domain R with torsion class group such that (R)=r.     

Left-inversion of combinatorial sums

The inversion of combinatorial sums is a fundamental problem in algebraic combinatorics. Some combinatorial sums, such as a_n = Σ_kd_n,kb_k, cannot be inverted in terms of the orthogonality relation because the infinite, lower triangular array P = {d_n,k}'s diagonal elements are equal to zero (except d_0,0). Despite this, we can find a left-inverse ̄P such that PP̄ = I and therefore are able to left-invert the original combinatorial sum, and thus obtain b_n = Σ_kd̄_n,ka_k.     

Art galleries with guards of uniform range of vision

We are given an art gallery represented by a simple polygon with n sides and an angle (0°,360°]. How many guards of range of vision are required to monitor every point of the polygon in the worst case? After recent results on upper bounds of this problem, we prove new lower bounds for all 0°<<180°. Several lower bounds meet the best known upper bounds, and we expect our lower bounds to be best possible.

Surprisingly, it turns out that n/3 180°-guards are always enough to monitor a polygon of n sides, but if we wish to use (180−)°-guards for any >0, then possibly 2n/3−1 guards are necessary.     

Function-space compactifications of function spaces

If X and Y are Hausdorff spaces with X locally compact, then the compact-open topology on the set C(X,Y) of continuous maps from X to Y is known to produce the right function-space topology. But it is also known to fail badly to be locally compact, even when Y is locally compact. We show that for any Tychonoff space Y, there is a densely injective space Z containing Y as a densely embedded subspace such that, for every locally compact space X, the set C(X,Z) has a compact Hausdorff topology whose relative topology on C(X,Y) is the compact-open topology. The following are derived as corollaries: (1) If X and Y are compact Hausdorff spaces then C(X,Y) under the compact-open topology is embedded into the Vietoris hyperspace V(X×Y). (2) The space of real-valued continuous functions on a locally compact Hausdorff space under the compact-open topology is embedded into a compact Hausdorff space whose points are pairs of extended real-valued functions, one lower and the other upper semicontinuous. The first application is generalized in two ways.     

Lower bounds for the size in four families of minimum broadcast graphs

In this paper, we give a lower bound for the size B(n) of a minimum broadcast graph of order n = 2^k − 4, 2^k − 6, 2^k − 5 or 2^k − 3 which is shown to be accurate in the cases when k = 5 and k = 6. This result provides, together with an upper bound obtained by a construction given in Bermond et al. (1992), an estimation of the value B(n) for n = 2^k − 4.     

Boundary Behavior of Large Solutions to the Monge-Ampère Equation in a Borderline Case

This paper is concerned with the boundary behavior of strictly convex large solutions to the Monge-Ampère equation detD²u(x)=b(x)f(u(x)), u > 0, x ∈ Ω, where Ω is a strictly convex and bounded smooth domain in R^N with N ≥ 2, f is normalized regularly varying at infinity with the critical index N and has a lower term, and b ∈ C^∞(Ω) is positive in Ω, but may be appropriate singular on the boundary.     

Prime power divisors of binomial coefficients

It is known that for sufficiently large n and m and any r the binomial coefficient (ⁿ_m) which is close to the middle coefficient is divisible by p^r where p is a ‘large’ prime. We prove the exact divisibility of (ⁿ_m) by p^r for p> c(n). The lower bound is essentially the best possible. We also prove some other results on divisibility of binomial coefficients.     

Degree conditions for Hamiltonian graphs to have [a,b]-factors containing a given Hamiltonian cycle

Let 1a<b be integers and G a Hamiltonian graph of order |G|(a+b)(2a+b)/b. Suppose that δ(G)a+2 and max{deg_G(x), deg_G(y)}a|G|/(a+b)+2 for each pair of nonadjacent vertices x and y in G. Then G has an [a,b]-factor which is edge-disjoint from a given Hamiltonian cycle. The lower bound on the degree condition is sharp. For the case of odd a=b, there exists a graph satisfying the conditions of the theorem but having no desired factor. As consequences, we have the degree conditions for Hamiltonian graphs to have [a,b]-factors containing a given Hamiltonian cycle.     

Walking an unknown street with bounded detour

A polygon with two distinguished vertices, s and g, is called a street if the two boundary chains from s to g are mutually weakly visible. For a mobile robot with on-board vision system we describe a strategy for finding a short path from s to g in a street not known in advance, and prove that the length of the path created does not exceed 1 + π times the length of the shortest path from s to g. Experiments suggest that our strategy is much better than this, as no ratio bigger than 1.8 has yet been observed. This is complemented by a lower bound of 1.41 for the relative detour each strategy can be forced to generate.     

Eigenvalue inequalities associated with the cartesian decomposition

Let T=A+iB where AB are Hermitian matrices. We obtain several inequalities relating the l_p distance between the eigenvalues of A and those of iB with the Schatten p-norm of T. The majorization results which lead to these inequalities are also used to get simple proofs of some known lower and upper bounds for the determinant of T.     

A note on formulations for the A-partition problem on hypergraphs

Let H = (V, E) be an undirected hypergraph and AC. We consider the problem of finding a minimum cost partition of V that separates every pair of nodes in A. We consider three formulations of the problem and show that the theoretical lower bounds to the integer optimal objective value provided by the LP-relaxations in all three cases are identical. We describe our empiical findings with each formulation.     

A note on the stationarity of a threshold first-order bilinear process

In the present note we study the threshold first-order bilinear model

X(t)=aX(t−1)+(b₁1_{X(t−1)<c}+b₂1_{X(t−1)c})X(t−1)e(t−1)+e(t), tεN

where {e(t), tεN} is a sequence of i.i.d. absolutely continuous random variables, X(0) is a given random variable and a, b₁, b₂ and c are real numbers. Under suitable conditions on the coefficients and lower semicontinuity of the densities of the noise sequence, we provide sufficient conditions for the existence of a stationary solution process to the present model and of its finite moments of order p.     

k-Subdomination in graphs

For a positive integer k, a k-subdominating function of a graph G=(V,E) is a function f : V→{−1,1} such that ∑_uNG[v]f(u)1 for at least k vertices v of G. The k-subdomination number of G, denoted by γ_ks(G), is the minimum of ∑_vVf(v) taken over all k-subdominating functions f of G. In this article, we prove a conjecture for k-subdomination on trees proposed by Cockayne and Mynhardt. We also give a lower bound for γ_ks(G) in terms of the degree sequence of G. This generalizes some known results on the k-subdomination number γ_ks(G), the signed domination number γ_s(G) and the majority domination number γ_maj(G).