Discrete Mathematics, Algorithms and Applications

Online and semi-online scheduling problems on a single machine with an availability constraint are considered in this paper. The machine has one unavailable interval in which jobs cannot be processed. Preemption is not allowed. Jobs arrive over time. The objective is to minimize makespan. First we discuss the online version of the problem. After giving its lower bound, we prove that Earliest Release Date (ERD) algorithm is an optimal algorithm. Then we study some semi-online problems in which the largest processing time, the total processing time, the largest release date, or the optimal makespan is known in advance. For these semi-online problems, we give their lower bounds, design semi-online algorithms and prove their competitive ratios, respectively.

In this paper we define the detour eccentric sequences and detour distance degree sequences of graphs. Some of the properties of these sequences are analyzed. It is observed that certain of these properties behave differently to their counterpart if defined using detour distance and these facts are established by providing suitable counterexamples. The concept of detour distance distributions in graphs is also discussed.

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination numberγ_t(G) is the minimum cardinality of a total dominating set of G. The game total domination subdivision number of a graph G is defined by the following game. Two players 𝒟 and 𝒜, 𝒟 playing first, alternately mark or subdivide an edge of G which is not yet marked nor subdivided. The game ends when all the edges of G are marked or subdivided and results in a new graph G′. The purpose of 𝒟 is to minimize the total domination number γ_t(G′) of G′ while 𝒜 tries to maximize it. If both 𝒜 and 𝒟 play according to their optimal strategies, γ_t(G′) is well defined. We call this number the game total domination subdivision number of G and denote it by γ_gt(G). In this paper we initiate the study of the game total domination subdivision number of a graph and present some (sharp) bounds for this parameter.

Let G = (V(G), E(G)) be a simple, finite and undirected graph of order n. Given a bijection f: V(G) ∪ E(G) → Z_k such that for each edge uv ∈ E(G), f(u) + f(v) + f(uv) is constant C(mod k). Let n_f(i) be the number of vertices and edges labeled by i under f. If |n_f(i) - n_f(j)| ≤ 1 for all 0 ≤ i < j ≤ k - 1, we say f is a k-totally magic cordial (k-TMC) labeling of G. A graph is said to be k-totally cordial magic if it admits a k-TMC labeling. In this paper, we give some ways to construct new families of k-TMC graphs from a known k-totally cordial magic graphs. We also give a sufficient condition for an odd graph to admit no k-TMC labeling. As a by-product, we determine the k-totally magic cordiality of many families of graphs.

Let ℕ₀ denote the set of all non-negative integers and 𝒫(ℕ₀) be its power set. An integer additive set-indexer (IASI) of a graph G is an injective function f : V(G) → 𝒫(ℕ₀) such that the induced function f⁺ : E(G) → 𝒫(ℕ₀) defined by f⁺ (uv) = f(u) + f(v) is also injective. A graph G which admits an IASI is called an integer additive set-indexed graph (IASI-graph). An IASI of a graph G is said to be an arithmetic IASI if the elements of the set-labels of all vertices and edges of G are in arithmetic progressions. In this paper, we discuss about two special types of arithmetic IASIs.

A 2-factorization {F₁, F₂,…,F_d} of a 2d-regular graph G such that each and the remaining F_i's are all Hamilton cycles is called Hamilton cycle rich 2-factorization of G, where G_i's are the given non-isomorphic 2-factors of G. In this paper, we prove that there exists a 2-factorization {F₁, F₂,…,F_n} of K_2n,2n such that F₁ ≅ G₁, F₂ ≅ G₂ and the remaining F_i's are Hamilton cycles of K_2n,2n, where G₁ and G₂ are the given two non-isomorphic 2-factors of K_2n,2n. In fact our result together with the earlier results settles the existence of Hamilton cycle rich 2-factorizations of K(m, p), the complete p-partite graph with m vertices in each partite set, except when (m, p) = (2n + 1, 2), in the case that two of the 2-factors are isomorphic to the given two non-isomorphic 2-factors and the remaining are Hamilton cycles.

Let R be a non-commutative ring and let C(R) be the center of R. The non-commuting graph Γ_R of R associated to R is defined as a graph with R\C(R) as the vertices and two distinct vertices x and y are joined whenever xy ≠ yx. We study various graph theoretical properties of this graph.

A finite word w ∈ {0, 1}* is balanced if for every equal-length factors u and v of every cyclic shift of w we have ||u|₁ - |v|₁| ≤ 1. This new class of finite words was defined in [O. Jenkinson and L. Q. Zamboni, Characterisations of balanced words via orderings, Theoret. Comput. Sci.310(1–3) (2004) 247–271]. In [O. Jenkinson, Balanced words and majorization, Discrete Math. Algorithms Appl.1(4) (2009) 463–484], there was proved several results considering finite balanced words and majorization. One of the main results was that the base-2 orbit of the balanced word is the least element in the set of orbits with respect to partial sum. It was also proved that the product of the elements in the base-2 orbit of a word is maximized precisely when the word is balanced. It turns out that the words 0^q-p1^p have similar extremal properties, opposite to the balanced words, which makes it meaningful to call these words the most unbalanced words. This paper contains the counterparts of the results mentioned above. We will prove that the orbit of the word u = 0^q-p1^p is the greatest element in the set of orbits with respect to partial sum and that it has the smallest product. We will also prove that u is the greatest element in the set of orbits with respect to partial product.

In this paper, we introduce new definitions of the Gray weight and the Gray map for linear codes over ℤ₉ + uℤ₉ with u² = u. Some results on self-dual codes over this ring are investigated. Further, the structural properties of quadratic residue codes are also considered. Two self-dual codes with new parameters [22, 11, 5] and [24, 12, 9] over ℤ₉ are obtained.

In this paper, we have defined ℤ_q-linear code and constructed some new codes. In particular, we have introduced the concept of ℤ_q-Simplex codes and proved that it is a -linear code for any integer q ≥ 2 and k ≥ 3 where p is the least order element in ℤ_q. We have given the weight distribution of ℤ_q-Simplex codes of dimension 2 when q is a prime power and when q is a product of distinct primes.

We consider prisms over complete 3-uniform hypergraphs and decompose them into Hamiltonian cycles of Katona–Kierstead type. We show that prisms over complete 3-uniform hypergraphs of order 4, 5 and 8 can be decomposed into Hamiltonian cycles and we suggest that prisms over complete 3-uniform hypergraphs of order in the form 6t + 2 may have Hamiltonian decompositions.

The pattern matching with wildcards and length constraints problem is an interesting problem in the literature whose computational complexity is still open. There are polynomial time exact algorithms for its special cases. There are heuristic algorithms, and online algorithms that do not guarantee an optimal solution to the original problem. We consider two special cases of the problem for which we develop offline solutions. We give an algorithm for one case with provably better worst case time complexity compared to existing algorithms. We present the first exact algorithm for the second case. This algorithm uses integer linear programming (ILP) and it takes polynomial time under certain conditions.

In this paper, we consider the problem of decomposing the edge set of the hypercube Q_n into two spanning, regular, connected, bipancyclic subgraphs. We prove that if n = n₁ + n₂ with n₁ ≥ 2 and n₂ ≥ 2, then the edge set of Q_n can be decomposed into two spanning, bipancyclic subgraphs H₁ and H₂ such that H_i is n_i-regular and n_i-connected for i = 1, 2.

Bermond conjectured that if G is Hamilton cycle decomposable, then L(G), the line graph of G is Hamilton cycle decomposable. In this paper, we prove that, for any k > 5, there exists a directed Hamilton cycle decomposable 2-diregular digraph D of order 2k such that L(D) is not directed Hamilton cycle decomposable.

The injective chromatic number χ_i(G) [G. Hahn, J. Kratochvil, J. Siran and D. Sotteau, On the injective chromatic number of graphs, Discrete Math. 256(1–2) (2002) 179–192] of a graph G is the minimum number of colors needed to color the vertices of G such that two vertices with a common neighbor are assigned distinct colors. The nature of the coefficients of injective chromatic polynomials of complete graphs, wheel graphs and cycles is studied. Injective chromatic polynomial on operations like union, join, product and corona of graphs is obtained.

We study the derangement number on a Ferrers board B = (n × n) - λ with respect to an initial permutation M, that is, the number of permutations on B that share no common points with M. We prove that the derangement number is independent of M if and only if λ is of rectangular shape. We characterize the initial permutations that give the minimal and maximal derangement numbers for a general Ferrers board, and present enumerative results when λ is a rectangle.

The influence maximization problem in social networks is to find a set of seed nodes such that the total influence effect is maximized under certain cascade models. In this paper, we propose a novel task of improving influence, which is to find strategies to allocate the investment budget under IC-N model. We prove that our influence improving problem is 𝒩𝒫-hard, and propose new algorithms under IC-N model. To the best of our knowledge, our work is the first one that studies influence improving problem under bounded budget when negative opinions emerge. Finally, we implement extensive experiments over a large data collection obtained from real-world social networks, and evaluate the performance of our approach.

For a poset P = (X, ≤_P), the strict-double-bound graphsDB(P) is the graph on X for which vertices u and v of sDB(P) are adjacent if and only if u ≠ v and there exist x and y in X distinct from u and v such that x ≤ _P u ≤ _P y and x ≤ _P v ≤ _P y. The strict-double-bound numberζ(G) of a graph G is defined as is a strict-double-bound graph}. We obtain that for a caterpillar Cat_n(m,m,…,m)(n ≥ 3). We also have that for

A set S ⊆ V(G) is an independent set if no two vertices of S are adjacent. An independent set S such that 〈V - S〉 is connected is called an outer-connected independent set(oci-set). An oci-set is maximal if it is not a proper subset of any oci-set. The minimum and maximum cardinality of a maximal oci-set are called respectively the outer-connected independence number and the upper outer-connected independence number. This paper initiates a study of these parameters.