Discrete Mathematics, Algorithms and Applications

The diameter of a graph can be affected by the addition or deletion of edges. In this paper, we examine the Cartesian product of graphs whose diameter increases (decreases) by the deletion (addition) of a single edge. The problems of minimality and maximality of the Cartesian product of graphs with respect to its diameter are also solved. These problems are motivated by the fact that most of the interconnection networks are graph products and a good network must be hard to disrupt and the transmissions must remain connected even if some vertices or edges fail.

We determine the exact value of the degree distance of the cartesian product and the wreath product of two graphs. Also we apply our results to compute the exact degree distance of hypercube, torus, grid, Hamming graph and fence graph.

A number of computations exist, especially in area of error-control coding and matrix computations, whose underlying data flow graphs are based on finite projective-geometry (PG) based balanced bipartite graphs. Many of these applications of finite projective geometry are actively being researched upon, especially in coding theory. Almost all these applications need large bipartite graphs, whose nodes represent parallel computations. To reduce its implementation cost, reducing amount of system/hardware resources during design is an important engineering objective. In this context, we present a scheme to reduce resource utilization while designing systems modeled using PG-based graphs. In such systems, the number of processing units is equal to the number of vertices, each performing an atomic computation. We present a novel way of partitioning the vertex set assigned to various atomic computations, into blocks. Each block of partition is then assigned to a processing unit. A processing unit performs the computations corresponding to the vertices in the block assigned to it in a sequential fashion, thus creating the effect of folding the overall computation. The symmetric properties of projective space lattices enable us to develop a conflict-free communication schedule. We employed the technique of coset decomposition of a finite field for partitioning. The folding scheme achieves the best possible throughput, in lack of any overhead of shuffling data across memories while scheduling another computation on the same processing unit. We first provide a scheme for a finite projective space of dimension five, and the corresponding schedules. This specific scheme is then generalized for arbitrary finite projective spaces. Both the folding schemes have been verified by both simulation as well as hardware prototyping. For example, a semi-parallel decoder architecture for a new class of expander codes was designed and implemented using this scheme, with potential deployment in DVD-R/CD-ROM drives.

Cournot competition model calculates profit by company's product quantity, but it does not take market share objective into consideration. It has obstacles of considering nonlinear aspects because the partial derivative equations are very hard to solve. Our algorithm both improves Cournot's model with consideration of market share ratio, and avoids the difficulty of solving several partial derivative equations directly. In our algorithm, we give a parameter σ to describe a company's consideration of market share objective, formulate the competition between companies, and calculate new market share ratio using parameter σ. We consider two network structures in our model: complete graph network and star graph network. For complete graph network, our calculation and numerical analysis is based on the case of 3 companies, but the result for general number of companies, n, is also discussed. We give a series of numerical results of new market share ratio after given the initial market share ratio and the parameter σ, and show that the initial market share ratio and new market share ratio are highly linear. Another important property in this network is the convergence of market share ratio when n goes to infinity. For star graph network, we give calculation for general cases and show that n = 3, 4 are the only numbers of companies that have positive increase of the market share ratio of the company.

An injective-k coloring of a graph G is a mapping cV(G) → {1, 2, …, k}, such that c(u) ≠ c(v) for each u, v ∈ V(G), whenever u, v have a common neighbor in G. If G has an injective-k coloring, then we call that G is injective-k colorable. Call χ_i(G) = min{k | G is injective-k colorable} is the injective chromatic number of G. Assign each vertex v ∈ V(G) a coloring set L(v), then L = {L(v) | v ∈ V(G)} is said to be a color list of G. Let L be a color list of G, if G has an injective coloring c such that c(v) ∈ L(v), ∀v ∈ V(G), then we call c an injective L-coloring of G. If for any color list L, such that |L(v)| ≥ k, G has an injective L-coloring, then G is said to be injective k-choosable. Call is injective k-choosable} is the injective chromatic number of G. So far, for the plane graph G of girth g(G) ≥ 5 and maximum degree Δ(G) ≥ 8, the best result of injective chromatic number is χ_i(G) ≤ Δ + 8. In this paper, for the plane graph G, we proved that if girth g(G) ≥ 5 and maximum degree Δ(G) ≥ 8.

In this paper, a new class of codes over GF(2) is introduced. The codes have length n = 3/2 ⋅ 2^m(m ≥ 4), and have a similar 'double inductive' structure to that possessed by the class of GRM and DGRM codes. The new codes are constructed in a way such that their length-to-distance ratio n/d = 2^m(m ≥ 3).

In this paper, we consider the series of Tribonacci numbers. Thereby, we introduce a new coding theory called Tribonacci coding theory based on Tribonacci numbers and show that in the simplest case, the correct ability of this method is 99.80% whereas the correct ability of the Fibonacci coding/decoding method is 93.33%.

In this paper, we develop hybrid matrix cryptography followed by Fibonacci Q_p,h(x) matrix, where h(x) is a polynomial with real coefficients and p = 1, 2, 3, …. They are the generalization of classical Fibonacci Q matrix for a continuous domain. They are used for designing super reliable cryptosystems.

In 2004, Karoński, Łuczak, and Thomason conjectured that the edges of any connected graph on at least 3 vertices may be weighted from the set {1, 2, 3} so that the vertices are properly colored by the sums of their incident edge weights. Bartnicki, Grytczuk and Niwcyk introduced its list version. Assign to each edge e ∈ E(G) a list of k real numbers, say L(e), and choose a weight w(e) ∈ L(e) for each e ∈ E(G). The resulting function w : E(G) → ⋃_e∈E(G) L(e) is called an edge k-list-weighting. Given a graph G, the smallest k such that any assignment of lists of size k to E(G) permits an edge k-list-weighting which is a vertex coloring by sums is denoted by and called the edge weight choosability of G. Bartnicki, Grytczuk and Niwcyk conjectured that if G is a nice graph (without a component isomorphic to K₂), then . There is no known constant K such that for any nice graph G. Ben Seamone proved that for any nice graph G with maximum degree Δ(G) by using Alon's Combinatorial Nullstellensatz. In this paper, we improve this bound to .

Given a set ℒ of non-parallel lines in the plane and a nonempty subset ℒ′ ⊆ ℒ, a guarding tree for ℒ′ is a tree contained in the union of the lines in ℒ such that if a mobile guard (agent) runs on the edges of the tree, all lines in ℒ′ are visited by the guard. Similarly, given a connected arrangement 𝒮 of line segments in the plane and a nonempty subset 𝒮′ ⊆ 𝒮, we define a guarding tree for 𝒮′. The minimum guarding tree problem for a given set of lines or line segments is to find a minimum-length guarding tree for the input set. We provide a simple alternative (to [N. Xu, Complexity of minimum corridor guarding problems, Inf. Process. Lett.112(17–18) (2012) 691–696.]) proof of the problem of finding a guarding tree of minimum length for a set of orthogonal (axis-parallel) line segments in the plane. Then, we present two approximation algorithms with factors 2 and 3.98, respectively, for computing a minimum guarding tree for a subset of a set of n arbitrary non-parallel lines in the plane; their running times are O(n⁸) and O(n⁶log n), respectively. Finally, we show that this problem is NP-hard for lines in 3-space.

In this paper, we generalize the concepts of Eulerian and Hamiltonian digraphs to directed hypergraphs. A dihypergraphH is a pair (𝒱(H), ℰ(H)), where 𝒱(H) is a non-empty set of elements, called vertices, and ℰ(H) is a collection of ordered pairs of subsets of 𝒱(H), called hyperarcs. It is Eulerian (resp. Hamiltonian) if there is a dicycle containing each hyperarc (resp. each vertex) exactly once. We first present some properties of Eulerian and Hamiltonian dihypergraphs. For example, we show that deciding whether a dihypergraph is Eulerian is an NP-complete problem. We also study when iterated line dihypergraphs are Eulerian and Hamiltonian. Finally, we study when the generalized de Bruijn dihypergraphs are Eulerian and Hamiltonian. In particular, we determine when they contain a complete Berge dicycle, i.e., an Eulerian and Hamiltonian dicycle.

In this paper, we construct a subclass of the composite access structure based on schemes realizing the structure given by the set of codewords of minimal support of linear codes. This class enlarges the iterated threshold class studied in the same paper and allow us to show a Brickell-like distribution scheme realizing those access structures.

Bicyclic graphs are connected graphs in which the number of edges equals the number of vertices plus one. The class of bicyclic graphs of order n, denoted by ℬ_n, can be partitioned into two subclasses: the class of graphs which contain induced ∞-graphs, and the class of graphs which contain induced θ-graphs. Bose et al. [2] have found the graph having the minimal distance spectral radius in . In this paper, we determine the graphs having the minimal distance spectral radius in . These results together give a complete characterization of the graphs having the minimal distance spectral radius in ℬ_n.

We characterize graphs with minimal distance spectral radius in two classes of graphs: with vertex connectivity k and minimum degree at least k, and with given number of blocks. Moreover, we determine the unique graph that maximizes the distance spectral radius among all graphs with given clique number.