Browse

You are looking at 91 - 100 of 604 items for :

  • Discrete Mathematics x
Clear All
Open access

Xiaodan Chen, Guoliang Hao and Lutz Volkmann

Abstract

Let k be a positive integer. A signed Roman k-dominating function (SRkDF) on a digraph D is a function f : V (D) → {−1, 1, 2} satisfying the conditions that (i) Σx∈N−[v]f(x) ≥ k for each v ∈ V (D), where N−[v] is the closed in-neighborhood of v, and (ii) each vertex u for which f(u) = −1 has an in-neighbor v for which f(v) = 2. The weight of an SRkDF f is Σv∈V (D)f(v). The signed Roman k-domination number γk sR(D) of a digraph D is the minimum weight of an SRkDF on D. We determine the exact values of the signed Roman k-domination number of some special classes of digraphs and establish some bounds on the signed Roman k-domination number of general digraphs. In particular, for an oriented tree T of order n, we show that γ2 sR(T) ≥ (n + 3)/2, and we characterize the oriented trees achieving this lower bound.

Open access

Wenjie Ning, Mei Lu and Kun Wang

Abstract

Suppose G = (V,E) is a graph with no isolated vertex. A subset S of V is called a locating-total dominating set of G if every vertex in V is adjacent to a vertex in S, and for every pair of distinct vertices u and v in V −S, we have N(u) ∩ S ≠ N(v) ∩ S. The locating-total domination number of G, denoted by γL t(G), is the minimum cardinality of a locating-total dominating set of G. The annihilation number of G, denoted by a(G), is the largest integer k such that the sum of the first k terms of the nondecreasing degree sequence of G is at most the number of edges in G. In this paper, we show that for any tree of order n ≥ 2, γL t(T) ≤ a(T) + 1 and we characterize the trees achieving this bound.

Open access

Jian-Hua Yin and Jing-Xin Guan

Abstract

A bipartite-split graph is a bipartite graph whose vertex set can be partitioned into a complete bipartite set and an independent set. The bipartite- splittance of an arbitrary bipartite graph is the minimum number of edges to be added or removed in order to produce a bipartite-split graph. In this paper, we show that the bipartite-splittance of a bipartite graph depends only on the degree sequence pair of the bipartite graph, and an easily computable formula for it is derived. As a corollary, a simple characterization of the degree sequence pair of bipartite-split graphs is also given.

Open access

Guozhen Zhang and Shiying Wang

Abstract

Let D = (V (D),A(D)) be a strongly connected digraph. An arc set S ⊆ A(D) is a restricted arc-cut of D if D − S has a non-trivial strong component D1 such that D − V (D1) contains an arc. The restricted arc- connectivity λ‘(D) is the minimum cardinality over all restricted arc-cuts of D. In [C. Balbuena, P. García-Vázquez, A. Hansberg and L.P. Montejano, On the super-restricted arc-connectivity of s-geodetic digraphs, Networks 61 (2013) 20-28], Balbuena et al. introduced the concept of super- λ‘ digraphs. In this paper, we first introduce the concept of the arc fault tolerance of a digraph D on the super- λ‘ property. We define a super- λ′ digraph D to be m-super- λ‘ if D − S is still super- λ‘ for any S ⊆ A(D) with |S| ≤ m. The maximum value of such m, denoted by Sλ’(D), is said to be the arc fault tolerance of D on the super- λ‘ property. Sλ’(D) is an index to measure the reliability of networks. Next we provide a necessary and sufficient condition for the Cartesian product of regular digraphs to be super- λ‘. Finally, we give the lower and upper bounds on S λ’(D) for the Cartesian product D of regular digraphs and give an example to show that the lower and upper bounds are best possible. In particular, the exact value of Sλ’(D) is obtained in special cases.

Open access

Douglas B. West and Jennifer I. Wise

Abstract

Two vertices of the k-dimensional hypercube Qkare antipodal if they differ in every coordinate. Edges uv and xy are antipodal if u is antipodal to x and v is antipodal to y. An antipodal edge-coloring of Qkis a 2- edge-coloring such that antipodal edges always have different colors. Norine conjectured that for k ≥ 2, in every antipodal edge-coloring of Qksome two antipodal vertices are connected by a monochromatic path. Feder and Subi proved this for k ≤ 5. We prove it for k ≤ 6.

Open access

Izolda Gorgol and Anna Lechowska

Abstract

Let ar(G,H) be the largest number of colors such that there exists an edge coloring of G with ar(G,H) colors such that each subgraph isomorphic to H has at least two edges in the same color. We call ar(G,H) the anti- Ramsey number for a pair of graphs (G,H). This notion was introduced by Erdős, Simonovits and Sόs in 1973 and studied in numerous papers. Hanoi graphs were introduced by Scorer, Grundy and Smith in 1944 as the model of the well known Tower of Hanoi puzzle. In the paper we study the anti-Ramsey number of Hanoi graphs and consider them both as the graph G and H. Among others we present the exact value of the anti-Ramsey number in case when both graphs are constructed for the same number of pegs.

Open access

Wayne Goddard, Robert Melville and Honghai Xu

Abstract

We define an almost-injective coloring as a coloring of the vertices of a graph such that every closed neighborhood has exactly one duplicate. That is, every vertex has either exactly one neighbor with the same color as it, or exactly two neighbors of the same color. We present results with regards to the existence of such a coloring and also the maximum (minimum) number of colors for various graph classes such as complete k-partite graphs, trees, and Cartesian product graphs. In particular, we give a characterization of trees that have an almost-injective coloring. For such trees, we show that the minimum number of colors equals the maximum degree, and we also provide a polynomial-time algorithm for computing the maximum number of colors, even though these questions are NP-hard for general graphs.

Open access

Ida Aichinger and Gerhard Larcher

Abstract

We study sets of bounded remainder for the billiard on the unit square. In particular, we note that every convex set S whose boundary is twice continuously differentiable with positive curvature at every point, is a bounded remainder set for almost all starting angles a and every starting point x. We show that this assertion for a large class of sets does not hold for all irrational starting angles α.

Open access

Gamaliel Cerda-Morales

Abstract

In this paper, we give quadratic approximation of generalized Tribonacci sequence {Vn}n ≥0 defined by Vn = rVn−1 + sV n−2 + tV n−3 (n ≥ 3) and use this result to give the matrix form of the n-th power of a companion matrix of {Vn}n ≥0. Then we re-prove the cubic identity or Cassini-type formula for {Vn} n ≥0 and the Binet’s formula of the generalized Tribonacci quaternions.

Open access

Joseph Rosenblatt and Mrinal Kanti Roychowdhury

Abstract

Quantization for a probability distribution refers to the idea of estimating a given probability by a discrete probability supported by a finite number of points. In this paper, firstly a general approach to this process is outlined using independent random variables and ergodic maps; these give asymptotically the optimal sets of n-means and the nth quantization errors for all positive integers n. Secondly two piecewise uniform distributions are considered on R: one with infinite number of pieces and one with finite number of pieces. For these two probability measures, we describe the optimal sets of n-means and the nth quantization errors for all n ∈ N. It is seen that for a uniform distribution with infinite number of pieces to determine the optimal sets of n-means for n ≥ 2 one needs to know an optimal set of (n − 1)-means, but for a uniform distribution with finite number of pieces one can directly determine the optimal sets of n-means and the nth quantization errors for all n ∈ N.