A total [k]-coloring of a graph $$G$$ G is a mapping $$\phi : V (G) \cup E(G)\rightarrow [k]=\{1, 2,\ldots , k\}$$ ϕ : V ( G ) ∪ E ( G ) → [ k ] = { 1 , 2 , … , k } such that any two adjacent or incident elements in $$V (G) \cup E(G)$$ V ( G ) ∪ E ( G ) receive different colors. Let $$f(v)$$ f ( v ) denote the sum of the color of a vertex $$v$$ v and the colors of all incident edges of $$v$$ v . A total $$[k]$$ [ k ] -neighbor sum distinguishing-coloring of $$G$$ G is a total $$[k]$$ [ k ] -coloring of $$G$$ G such that for each edge $$uv\in E(G)$$ u v ∈ E ( G ) , $$f(u)\ne f(v)$$ f ( u ) ≠ f ( v ) . By $$\chi ^{''}_{nsd}(G)$$ χ n s d ′ ′ ( G ) , we denote the smallest value $$k$$ k in such a coloring of $$G$$ G . Pilśniak and Woźniak conjectured $$\chi _{nsd}^{''}(G)\le \Delta (G)+3$$ χ n s d ′ ′ ( G ) ≤ Δ ( G ) + 3 for any simple graph with maximum degree $$\Delta (G)$$ Δ ( G ) . In this paper, we prove that this conjecture holds for any planar graph with maximum degree at least 13.

In recent years the unconstrained binary quadratic program (UBQP) has grown in importance in the field of combinatorial optimization due to its application potential and its computational challenge. Research on UBQP has generated a wide range of solution techniques for this basic model that encompasses a rich collection of problem types. In this paper we survey the literature on this important model, providing an overview of the applications and solution methods.

We generalize Laplacian matrices for graphs to Laplacian tensors for even uniform hypergraphs and set some foundations for the spectral hypergraph theory based upon Laplacian tensors. Especially, algebraic connectivity of an even uniform hypergraph based on Z-eigenvalues of the corresponding Laplacian tensor is introduced and its connections with edge connectivity and vertex connectivity are discussed.

We study a novel “coverage by directional sensors” problem with tunable orientations on a set of discrete targets. We propose a Maximum Coverage with Minimum Sensors (MCMS) problem in which coverage in terms of the number of targets to be covered is maximized whereas the number of sensors to be activated is minimized. We present its exact Integer Linear Programming (ILP) formulation and an approximate (but computationally efficient) centralized greedy algorithm (CGA) solution. These centralized solutions are used as baselines for comparison. Then we provide a distributed greedy algorithm (DGA) solution. By incorporating a measure of the sensors residual energy into DGA, we further develop a Sensing Neighborhood Cooperative Sleeping (SNCS) protocol which performs adaptive scheduling on a larger time scale. Finally, we evaluate the properties of the proposed solutions and protocols in terms of providing coverage and maximizing network lifetime through extensive simulations. Moreover, for the case of circular coverage, we compare against the best known existing coverage algorithm.

A grid computing system consists of a group of programs and resources that are spread across machines in the grid. A grid system has a dynamic environment and decentralized distributed resources, so it is important to provide efficient scheduling for applications. Task scheduling is an NP-hard problem and deterministic algorithms are inadequate and heuristic algorithms such as particle swarm optimization (PSO) are needed to solve the problem. PSO is a simple parallel algorithm that can be applied in different ways to resolve optimization problems. PSO searches the problem space globally and needs to be combined with other methods to search locally as well. In this paper, we propose a hybrid-scheduling algorithm to solve the independent task-scheduling problem in grid computing. We have combined PSO with the gravitational emulation local search (GELS) algorithm to form a new method, PSO–GELS. Our experimental results demonstrate the effectiveness of PSO–GELS compared to other algorithms.

In this paper, we investigate the Laplacian, i.e., the normalized Laplacian tensor of a $$k$$ -uniform hypergraph. We show that the real parts of all the eigenvalues of the Laplacian are in the interval $$[0,2]$$ , and the real part is zero (respectively two) if and only if the eigenvalue is zero (respectively two). All the H $$^+$$ -eigenvalues of the Laplacian and all the smallest H $$^+$$ -eigenvalues of its sub-tensors are characterized through the spectral radii of some nonnegative tensors. All the H $$^+$$ -eigenvalues of the Laplacian that are less than one are completely characterized by the spectral components of the hypergraph and vice verse. The smallest H-eigenvalue, which is also an H $$^+$$ -eigenvalue, of the Laplacian is zero. When $$k$$ is even, necessary and sufficient conditions for the largest H-eigenvalue of the Laplacian being two are given. If $$k$$ is odd, then its largest H-eigenvalue is always strictly less than two. The largest H $$^+$$ -eigenvalue of the Laplacian for a hypergraph having at least one edge is one; and its nonnegative eigenvectors are in one to one correspondence with the flower hearts of the hypergraph. The second smallest H $$^+$$ -eigenvalue of the Laplacian is positive if and only if the hypergraph is connected. The number of connected components of a hypergraph is determined by the H $$^+$$ -geometric multiplicity of the zero H $$^+$$ -eigenvalue of the Lapalacian.

An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph G, denoted rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In the first result of this paper we prove that computing rc(G) is NP-Hard solving an open problem from Caro et al. (Electron. J. Comb. 15, 2008, Paper R57). In fact, we prove that it is already NP-Complete to decide if rc(G)=2, and also that it is NP-Complete to decide whether a given edge-colored (with an unbounded number of colors) graph is rainbow connected. On the positive side, we prove that for every ε>0, a connected graph with minimum degree at least ε n has bounded rainbow connection, where the bound depends only on ε, and a corresponding coloring can be constructed in polynomial time. Additional non-trivial upper bounds, as well as open problems and conjectures are also presented.

To access, purchase, authenticate, or subscribe to the full-text of this article, please visit this link: http://dx.doi.org/10.1007/s10878-015-9896-4 In this paper, we study some extremal problems of three kinds of spectral radii of k k -uniform hypergraphs (the adjacency spectral radius, the signless Laplacian spectral radius and the incidence Q Q -spectral radius). We call a connected and acyclic k k -uniform hypergraph a supertree. We introduce the operation of "moving edges" for hypergraphs, together with the two special cases of this operation: the edge-releasing operation and the total grafting operation. By studying the perturbation of these kinds of spectral radii of hypergraphs under these operations, we prove that for all these three kinds of spectral radii, the hyperstar S.sub.n,k S n , k attains uniquely the maximum spectral radius among all k k -uniform supertrees on n n vertices. We also determine the unique k k -uniform supertree on n n vertices with the second largest spectral radius (for these three kinds of spectral radii). We also prove that for all these three kinds of spectral radii, the loose path P.sub.n,k P n , k attains uniquely the minimum spectral radius among all k k -th power hypertrees of n n vertices. Some bounds on the incidence Q Q -spectral radius are given. The relation between the incidence Q Q -spectral radius and the spectral radius of the matrix product of the incidence matrix and its transpose is discussed.

This paper addresses the problem of modifying the edge lengths of a tree in minimum total cost such that a prespecified vertex becomes the 1-center of the perturbed tree. This problem is called the inverse 1-center problem on trees. We focus on the problem under Chebyshev norm and Hamming distance. From special properties of the objective functions, we can develop combinatorial algorithms to solve the problem. Precisely, if there does not exist any vertex coinciding with the prespecified vertex during the modification of edge lengths, the problem under Chebyshev norm or bottleneck Hamming distance is solvable in $$O(n\log n)$$ O ( n log n ) time, where $$n+1$$ n + 1 is the number of vertices of the tree. Dropping this condition, the problem can be solved in $$O(n^{2})$$ O ( n 2 ) time.

Composite event detection is one of the fundamental tasks for heterogeneous wireless sensor networks (WSNs). Multi-modal data generated by heterogeneous sensors bring new challenges for composite event monitoring in heterogeneous WSNs. By exploiting the correlations between different types of data, the approximate composite event detection problem is investigated in this paper. The optimal transmitting scheme problem is proposed to calculate the optimal transmitting scheme with minimum cost on the constraint that the confidence of the composite event must exceed the threshold. The optimal transmitting scheme problem is proved to belong to NP-complete. A dynamic programming based algorithm is presented for simple linear confidence combination operators, which runs in pseudo-polynomial time. The greedy based approximate algorithm is also designed for general confidence combination operators and the approximate ratio is proved to be 2 for “+” as the confidence combination operator. The simulation results show that our algorithms can reduce energy consumption significantly.

When deploying sensors to monitor boundaries of battlefields or country borders, sensors are usually dispersed from an aircraft following a predetermined path. In such scenarios sensing gaps are usually unavoidable. We consider a wireless sensor network consisting of directional sensors deployed using the line-based sensor deployment model. In this paper we propose distributed algorithms for weak and strong barrier coverage that allow sensors to determine their orientation such that the total number of gaps is minimized. We use simulations to analyze the performance of our algorithms and to compare them with related works.

Data aggregation is an essential yet time-consuming task in wireless sensor networks. This paper studies the well-known minimum-latency aggregation schedule problem and proposes an energy-efficient distributed scheduling algorithm named Clu-DDAS based on a novel cluster-based aggregation tree. Our approach differs from all the previous schemes where connected dominating sets or maximal independent sets are employed. This paper proves that Clu-DDAS has a latency bound of $$4R'+2 \varDelta -2$$ 4 R ′ + 2 Δ - 2 , where $$\varDelta $$ Δ is the maximum degree and $$R'$$ R ′ is the inferior network radius which is smaller than the network radius $$R$$ R . Our experiments show that Clu-DDAS has an approximate latency upper bound of $$4R'+1.085 \varDelta -2$$ 4 R ′ + 1.085 Δ - 2 with increased $$\varDelta $$ Δ . Clu-DDAS has comparable latency as the previously best centralized algorithm, E-PAS, but consumes 78 % less energy as shown by the simulation results. Clu-DDAS outperforms the previously best distributed algorithm, DAS, whose latency bound is $$16R'+\varDelta -14$$ 16 R ′ + Δ - 14 on both latency and energy consumption. On average, Clu-DDAS transmits 67 % fewer total messages than DAS. The paper also proposes an adaptive strategy for updating the schedule to accommodate dynamic network topology.

In this paper, we study some extremal problems of three kinds of spectral radii of -uniform hypergraphs (the adjacency spectral radius, the signless Laplacian spectral radius and the incidence -spectral radius). We call a connected and acyclic -uniform hypergraph a supertree. We introduce the operation of "moving edges" for hypergraphs, together with the two special cases of this operation: the edge-releasing operation and the total grafting operation. By studying the perturbation of these kinds of spectral radii of hypergraphs under these operations, we prove that for all these three kinds of spectral radii, the hyperstar attains uniquely the maximum spectral radius among all -uniform supertrees on vertices. We also determine the unique -uniform supertree on vertices with the second largest spectral radius (for these three kinds of spectral radii). We also prove that for all these three kinds of spectral radii, the loose path attains uniquely the minimum spectral radius among all -th power hypertrees of vertices. Some bounds on the incidence -spectral radius are given. The relation between the incidence -spectral radius and the spectral radius of the matrix product of the incidence matrix and its transpose is discussed.

Tree representations of (sets of) symmetric binary relations, or equivalently edge-colored undirected graphs, are of central interest, e.g. in phylogenomics. In this context symbolic ultrametrics play a crucial role. Symbolic ultrametrics define an edge-colored complete graph that allows to represent the topology of this graph as a vertex-colored tree. Here, we are interested in the structure and the complexity of certain combinatorial problems resulting from considerations based on symbolic ultrametrics, and on algorithms to solve them.This includes, the characterization of symbolic ultrametrics that additionally distinguishes between edges and non-edges of arbitrary edge-colored graphs G and thus, yielding a tree representation of G, by means of so-called cographs. Moreover, we address the problem of finding “closest” symbolic ultrametrics and show the NP-completeness of the three problems: symbolic ultrametric editing, completion and deletion. Finally, as not all graphs are cographs, and hence, do not have a tree representation, we ask, furthermore, what is the minimum number of cotrees needed to represent the topology of an arbitrary non-cograph G. This is equivalent to find an optimal cograph edge k-decomposition $$\{E_1,\dots ,E_k\}$$ {E1,⋯,Ek} of E so that each subgraph $$(V,E_i)$$ (V,Ei) of G is a cograph. We investigate this problem in full detail, resulting in several new open problems, and NP-hardness results.For all optimization problems proven to be NP-hard we will provide integer linear program formulations to solve them.

This paper provides a comprehensive survey of research on operating room planning and scheduling problems. Aiming to give a comprehensive classification on the studied problems, we review the literature from the perspectives of decision level, scheduling strategy, patient characteristics, problem setting, uncertainty, mathematical models, and solutions and methods. The papers are reviewed in diversified ways so as to obtain a detailed overview in this area, and the fields that need to be focused on are summarized. It shows that mathematical programming and heuristics are frequently applied in the complex linear and combinatorial optimization problems. Furthermore, future research trends and directions on operating room planning and scheduling are also identified.

An oriented graph $$G^\sigma $$ Gσ is a digraph without loops or multiple arcs whose underlying graph is G. Let $$S\left( G^\sigma \right) $$ SGσ be the skew-adjacency matrix of $$G^\sigma $$ Gσ and $$\alpha (G)$$ α(G) be the independence number of G. The rank of $$S(G^\sigma )$$ S(Gσ) is called the skew-rank of $$G^\sigma $$ Gσ , denoted by $$sr(G^\sigma )$$ sr(Gσ) . Wong et al. (Eur J Comb 54:76–86, 2016) studied the relationship between the skew-rank of an oriented graph and the rank of its underlying graph. In this paper, the correlation involving the skew-rank, the independence number, and some other parameters are considered. First we show that $$sr(G^\sigma )+2\alpha (G)\geqslant 2|V_G|-2d(G)$$ sr(Gσ)+2α(G)⩾2|VG|-2d(G) , where $$|V_G|$$ |VG| is the order of G and d(G) is the dimension of cycle space of G. We also obtain sharp lower bounds for $$sr(G^\sigma )+\alpha (G),\, sr(G^\sigma )-\alpha (G)$$ sr(Gσ)+α(G),sr(Gσ)-α(G) , $$sr(G^\sigma )/\alpha (G)$$ sr(Gσ)/α(G) and characterize all corresponding extremal graphs.

Chamfer distances on the isometric grid are considered. A new method to compute the chamfer distances based on linear optimization is presented. In the LP model the starting pixel is the Origin, that is a triangle of the grid having co-ordinates (0, 0, 0). The co-ordinates of the end pixel of the path give the right-hand side of the model. The variables are the used numbers of the elementary steps. Each type of an elementary step has a uniquely defined weight. Our operational research approach determines the optimal paths as basic feasible solutions of a linear programming problem. We give directed graphs with feasible bases as nodes and arcs with conditions on the used weights such that the simplex method of linear programming may step from one feasible basis to another feasible basis. Thus, the possible course of the simplex method can be followed and the optimal bases can easily be captured. Thus, the final result of the analysis is an O(1) checking of the feasibility and optimality conditions. The optimal bases are summarized in a theorem which is the consequence of the general theory of linear programming. The method can be applied for other grids, but it needs to be adjusted for the particular grid.

A subset S of vertices in a graph G is a dominating set if every vertex in $$V(G) {\setminus } S$$ V ( G ) \ S is adjacent to a vertex in S. If the graph G has no isolated vertex, then a semipaired dominating set of G is a dominating set of G with the additional property that the set S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number $$\gamma _{\mathrm{pr2}}(G)$$ γ pr 2 ( G ) is the minimum cardinality of a semipaired dominating set of G. Let G be a maximal outerplanar graph of order n with $$n_2$$ n 2 vertices of degree 2. We show that if $$n \ge 5$$ n ≥ 5 , then $$\gamma _{\mathrm{pr2}}(G) \le \frac{2}{5}n$$ γ pr 2 ( G ) ≤ 2 5 n . Further, we show that if $$n \ge 3$$ n ≥ 3 , then $$\gamma _{\mathrm{pr2}}(G) \le \frac{1}{3}(n+n_2)$$ γ pr 2 ( G ) ≤ 1 3 ( n + n 2 ) . Both bounds are shown to be tight.

In this paper, we investigate the packing parameters in graphs. By applying the Mantel’s theorem, we give upper bounds on packing and open packing numbers of triangle-free graphs along with characterizing the graphs for which the equalities hold and exhibit sharp Nordhaus–Gaddum type inequalities for packing numbers. We also solve the open problem of characterizing all connected graphs with $$\rho _{o}(G)=n-\omega (G)$$ ρ o ( G ) = n - ω ( G ) posed in Hamid and Saravanakumar (Discuss Math Graph Theory 35:5–16, 2015).