# Journal of Combinatorial Optimization

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 252-263

*p*facilities (resources) on a network (or a graph) such that the subnetwork (or subgraph) induced by the selected set $$X_p$$ Xp is connected. Two problems on a block graph

*G*are proposed: one problem is to minimizes the sum of its weighted distances from all vertices of

*G*to $$X_p$$ Xp , another problem is to minimize the...

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 13-22

*G*is edge-

*k*-choosable if whenever every edge

*x*is assigned with a list of at least

*k*colors,

*L*(

*x*)), there exists an edge coloring $$\phi $$ ϕ such that $$\phi (x) \in L(x)$$ ϕ(x)∈L(x) . Similarly, A graph...

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 55-64

*k*-coloring of a graph

*G*is a proper

*k*-coloring such that any two vertices at distance two get different colors. $$\chi _{2}(G)$$ χ2(G) =min{

*k*|

*G*has a 2-distance

*k*-coloring}. Wegner conjectured that for each planar graph

*G*with maximum degree $$\Delta $$ Δ , $$\chi _2(G) \le 7$$ χ2(G)≤7 if $$\Delta \le 3$$ Δ≤3 , $$\chi _2(G) \le \Delta +5$$ χ2(G)≤Δ+5 if $$4\le \Delta \le 7$$ 4≤Δ≤7 and...

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 1-12

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 90-107

*nested compatibility*condition in acyclic digraphs. We then apply these results to

*optimum convex polygon*problems in...

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 23-34

*k*-coloring $$\phi $$ ϕ of a graph

*G*is a mapping from $$V(G)\cup E(G)$$ V(G)∪E(G) to $$\{1,2,\dots , k\}$$ {1,2,⋯,k} such that no adjacent or incident elements in $$V(G)\cup E(G)$$ V(G)∪E(G) receive the same color. Let $$m_{\phi }(v)$$ mϕ(v) denote the sum of the colors on the edges incident with the vertex

*v*and the color on

*v*. A proper total

*k*-coloring of

*G*is called neighbor...

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 65-80

*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...

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 307-328

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 81-89

*double Roman dominating function*(DRDF) on a graph $$G=(V,E)$$ G=(V,E) is a function $$f : V \rightarrow \{0, 1, 2, 3\}$$ f:V→{0,1,2,3} having the property that if $$f(v) = 0$$ f(v)=0 , then vertex

*v*must have at least two neighbors assigned 2 under

*f*or one neighbor

*w*with $$f(w)=3$$ f(w)=3 , and if $$f(v)=1$$ f(v)=1 , then vertex

*v*must have at least one neighbor

*w*with $$f(w)\ge 2$$ f(w)≥2...

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 35-43

*k*-path vertex cover ($$\hbox {VCP}_k$$ VCPk ) has received a lot of attention in recent years. Given a graph $$G=(V,E)$$ G=(V,E) , a vertex set $$C\subseteq V$$ C⊆V is a

*k*-path vertex cover ($$\hbox {VCP}_k$$ VCPk ) of

*G*if every path on

*k*vertices has at least one vertex in

*C*, and

*C*is a connected

*k*-path vertex cover...

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 44-54

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 130-130

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 211-229

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 142-161

*general*number of

*similar*jobs, where the processing times of the same step are independently drawn from a known probability distribution, and the objective is to minimize the makespan. For the stochastic problem, we introduce the fluid relaxation of its deterministic counterpart, and define a fluid schedule for the fluid...

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 162-193

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 194-210

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 108-120

*G*is a proper edge coloring of

*G*such that any pair of vertices at distance 2 have distinct sets of colors. The 2-distance vertex-distinguishing index $$\chi ^{\prime }_{\mathrm{d2}}(G)$$ χd2′(G) of

*G*is the minimum number of colors needed for a 2-distance vertex-distinguishing edge coloring of

*G*. Some network problems can be converted to...

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 131-141

*B*, a bipartite graph

*G*with parts

*S*and $$T \cup \{r\}$$ T∪{r} in a metric space and functions $$l_i :S \rightarrow {\mathbb {Z}}_+$$ li:S→Z+ and $${u_j :T \rightarrow \mathbb {Z}_+ \cup \{\infty \}}$$ uj:T→Z+∪{∞} , one wishes to find a set of

*B*walks in

*G*. Every walk in

*B*should start at

*r*and finish in

*T*and

*r*must be visited only...

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 264-279

*k*-facility location problem with linear penalties. In contrast to the classical facility location problem, this problem opens no more than

*k*facilities and pays a penalty cost for any non-served client. We present a local search algorithm for this problem with a similar but more technical analysis due to the...

Journal of Combinatorial Optimization > 2018 > 36 > 1 > 121-129

*G*, that is denoted by $$\lambda (G)$$ λ(G) , is the largest eigenvalue of

*G*. Let

*k*and $$n_1,\ldots ,n_k$$ n1,…,nk be some positive integers. Let $$T(n_1,\ldots ,n_k)$$ T(n1,…,nk) be the tree

*T*(

*T*is a path or a starlike tree) such that

*T*has a vertex

*v*so that $$T{\setminus } v$$ T\v is...