Discrete Mathematics, Algorithms and Applications

Let S be a set of points in the plane, such that the unit disk graph with vertex set S is connected. We address the problem of finding orientations and a minimum radius for directional antennas of a fixed cone angle placed at the points of S, such that the induced communication graph G[S] is a hop t-spanner of the unit disk graph for S (meaning that G[S] is strongly connected, and contains a directed path with at most t edges between any pair of points within unit distance). We consider problem instances in which antenna angles are bounded below by 120° and 90°. We show that, in the case of 120° angles, a radius of 5 suffices to establish a hop 4-spanner; and in the case of 90° angles, a radius of 7 suffices to establish a hop 5-spanner.

A set S of vertices of a graph G is a total outer-connected dominating set if every vertex in V(G) is adjacent to some vertex in S and the subgraph G[V\S] induced by V\S is connected. The total outer-connected domination numberγ_toc(G) is the minimum size of such a set. The total outer-connected domination subdivision numbersd_γtoc(G) is the minimum number of edges that must be subdivided in order to increase the total outer-connected domination number. We prove the existence of sd_γtoc(G) for every connected graph G of order at least 3 and give upper bounds on it in some classes of graphs.

Given an undirected graph G = (V, E) with n vertices and a positive length w(e) on each edge e ∈ E, we consider Minimum Average Distance (MAD) spanning trees i.e., trees that minimize the path length summed over all pairs of vertices. One of the first results on this problem is due to Wong who showed in 1980 that a Distance Preserving (DP) spanning tree rooted at the median of G is a 2-approximate solution. On the other hand, Dankelmann has exhibited in 2000 a class of graphs where no MAD spanning tree is distance preserving from a vertex. We establish here a new relation between MAD and DP trees in the particular case where the lengths are integers. We show that in a MAD spanning tree of G, each subtree H′ = (V′, E′) consisting of a vertex and the union of branches of that are each of size less than or equal to , where w⁺ is the maximum edge-length in G, is a distance preserving spanning tree of the subgraph of G induced by V′.

Motivated by the article in Scientific American [7], Michael A Henning and Stephen T Hedetniemi explored the strategy of defending the Roman Empire. Cockayne defined Roman dominating function (RDF) on a Graph G = (V, E) to be a function f : V → {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. For a real valued function f : V → R the weight of f is w(f) = ∑_v∈V f(v). The Roman domination number (RDN) denoted by γ_R(G) is the minimum weight among all RDF in G. If V – D contains a roman dominating function f¹ : V → {0, 1, 2}. "D" is the set of vertices v for which f(v) > 0. Then f¹ is called Inverse Roman Dominating function (IRDF) on a graph G w.r.t. f. The inverse roman domination number (IRDN) denoted by is the minimum weight among all IRDF in G. In this paper we find few results of IRDN.

Let G be a graph. The gamma graph of G denoted by γ ⋅ G is the graph with vertex set V(γ ⋅ G) as the set of all γ-sets of G and two vertices D and S of γ ⋅ G are adjacent if and only if |D ∩ S| = γ(G) – 1. A graph H is said to be a γ-graph if there exists a graph G such that γ ⋅ G is isomorphic to H. In this paper, we show that every induced subgraph of a γ-graph is also a γ-graph. Furthermore, if we prove that H is a γ-graph, then there exists a sequence {G_n} of non-isomorphic graphs such that H = γ ⋅ G_n for every n.

We present an alternative implementation of the (1 – ϵ) factor NC approximation algorithm for the maximum weight matching by Hougardy et al. [1]. Our implementation, on the EREW PRAM model of computation, achieves an factor improvement on both the execution time and the number of processors.

Trees are very common in the theory and applications of combinatorics. In this paper, we consider graphs whose underlying structure is a tree and study the behavior of the distance spectral radius under a graph transformation. As an application, we find the corona tree that maximizes the distance spectral radius among all corona trees with a fixed maximum degree. We also find the graph with minimal (maximal) distance spectral radius among all corona trees. Finally, we determine the graph with minimal distance spectral radius in a special class of corona trees.

The graphs in which every minimal vertex separator induces a complete or an edgeless subgraph are shown to be the edge sums of graphs of the two extreme types: (i) when every minimal vertex separator induces a complete subgraph — these are precisely the well-studied chordal graphs — and (ii) when every minimal vertex separator induces an edgeless subgraph — these have appeared in several recent papers.

We investigate (v, k, λ) difference sets with k < 350, n = k – λ = m², where m = 5, 8, 9, 11, 13, 14 and v ≡ 0 mod 68. By applying methods in algebraic number theory, group representations and rational idempotents of the group ring, we conclude that most of the groups of order v do not admit the respective difference sets.

The independence number of a graph is defined as the maximum size of a set of pairwise non-adjacent vertices and the spectral radius is defined as the maximum eigenvalue of the adjacency matrix of the graph. Xu et al. in [The minimum spectral radius of graphs with a given independence number, Linear Algebra and its Applications431 (2009) 937–945] determined the connected graphs of order n with independence number which minimize the spectral radius. In this paper, we show that the graph obtained from a path of order α by blowing up each vertex to a clique of order k minimizes the spectral radius among all connected graphs of order kα with independence number α for α = 3, 4 and conjecture that this is true for all α ∈ ℕ.

Two vertices u, w ∈ V, vv-dominate each other if they are incident on the same block. A set S ⊆ V is a vv-dominating set (VVD-set) if every vertex in V – S is vv-dominated by a vertex in S. The vv-domination number γ_vv = γ_vv(G) is the cardinality of a minimum VVD-set of G. Two blocks b₁, b₂ ∈ B(G) the set of all blocks of G, bb-dominate each other if there is a common cutpoint. A set L ⊆ B(G) is said to be a bb-dominating set (BBD set) if every block in B(G) – L is bb-dominated by some block in L. The bb-domination number γ_bb = γ_bb(G) is the cardinality of a minimum BBD-set of G. A vertex v and a block b are said to b-dominate each other if v is incident on the block b. Then vb-domination number γ_vb = γ_vb(G) (bv-domination number γ_bv = γ_bv(G)) is the minimum number of vertices (blocks) needed to b-dominate all the blocks (vertices) of G. In this paper we study the properties of these block domination parameters and establish a relation between these parameters giving an inequality chain consisting of nine parameters.

The majorization polytope M(a) consists of all vectors dominated (or majorized, to be precise) by a given vector a ∈ ℝⁿ; this is a polytope with extreme points being the permutations of a. For integral vector a, let ν(a) be the number of integral vectors contained in M(a). We present several properties of the function ν and provide an algorithm for computing ν(a).

While indices, index tracking funds and ETFs have grown in popularity during then last ten years, there are many structural problems, tracking errors and biases inherent in index calculation methodologies and the legal/economic structure of ETFs, which raise actionable issues of "suitability" and "fraud" under US securities laws. This article contributes to the existing literature by: (a) introducing and characterizing the errors and biases inherent in "risk-adjusted" index-weighting methods and the associated adverse effects; (b) showing how these biases/effects reduce social welfare, and can facilitate harmful arbitrage activities; (c) introducing new theorems.

Given a set of points P = {p₁, p₂, …, p_n} in the Euclidean plane, with each point p_i associated with a given direction v_i ∈ V. P(p_i, v_i) defines a half-plane and L(p_i, v_i) denotes the baseline that is perpendicular to v_i and passing through p_i. Define a region dominated by p_i and v_i as a Baseline Bounded Half-Plane Voronoi Region, denoted as V or(p_i, v_i), if a point x ∈ V or(p_i, v_i), then (1) x ∈ P(p_i, v_i); (2) the line segment l(x, p_i) does not cross any baseline; (3) if there is a point p_j, such that x ∈ P(p_j, v_j), and the line segment l(x, p_j) does not cross any baseline then d(x, p_i) ≤ d(x, p_j), j ≠ i. The Baseline Bounded Half-Plane Voronoi Diagram, denoted as V or(P, V), is the union of all V or(p_i, v_i). We show that V or(p_i, v_i) and V or(P, V) can be computed in O(n log n) and O(n²log n) time, respectively. For the heterogeneous point set, the same problem is also considered.