Search

Considering the appointments that teachers plan to teach some courses for specific classes, the problem is to schedule the curriculum such that the time for each teacher is consecutive. In this work, we propose an integer linear programming model to solve consecutive interval edge-coloring of a graph. By using the proposed method, we give the interval edge colorability of some small complete multipartite graphs. Moreover, we find some new classes of complete multipartite graphs that have interval edge-colorings and disprove a conjecture proposed by Grzesik and Khachatrian (2014).

A Roman {2}-dominating function (R{2}DF) on a graph G =(V, E) is a function f : V → {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to either at least one vertex v with f(v) = 2 or two vertices v1, v2 with f(v1) = f(v2) = 1. The weight of an R{2}DF f is the value w(f) = ∑u∈Vf(u). The minimum weight of an R{2}DF on a graph G is called the Roman {2}-domination number γ{R2}(G) of G. An R{2}DF f is called an independent Roman {2}-dominating function (IR{2}DF) if the set of vertices with positive weight under f is independent. The minimum weight of an IR{2}DF on a graph G is called the independent Roman {2}-domination number i{R2}(G) of G. In this paper, we answer two questions posed by Rahmouni and Chellali.

An acyclic coloring of a graph is a proper coloring of the graph, for which every cycle uses at least three colors. Let G 4 be the set of maximal planar graphs of minimum degree 4, such that each graph in G 4 contains exactly four odd-vertices and the subgraph induced by the four odd-vertices contains a quadrilateral. In this article, we show that every acyclic 4-coloring of a maximal planar graph with exact four odd-vertices is locally equitable with regard to its four odd-vertices. Moreover, we obtain a necessary and sufficient condition for a graph in G 4 to be acyclically 4-colorable, and give an enumeration of the acyclically 4-colorable graphs in G 4 .

An acyclic colouring of a graph is a proper colouring of the graph, for which every cycle uses at least three colours. In this paper, we describe a method for constructing all 4-connected acyclically 4-colourable planar triangulations that have exactly four odd-vertices, except the ones that contain no adjacent odd-vertices. Unlike previous operations, our method successfully establishes a connection with (acyclic) 4-colourings. Moreover, we discuss a special class of graphs, called diamond triangulations, and give a necessary and sufficient condition for a diamond triangulation to be acyclically 4-colourable.

We study the local k-coloring of graphs.We prove that it is NP-complete to determine whether a graph has a local k-coloring for fixed k=4 or k=2t1, where t3.We prove that it is NP-complete to determine whether a planar graph has a local 5-coloring even restricted to the maximum degree =7or8. A local k-coloring of a graph G is a function f:V(G){1,2,,k} such that for each SV(G), 2|S|3, there exist u,vS with |f(u)f(v)| at least the size of the subgraph induced by S. The local chromatic number of G is (G)=min{k:Ghas a localk-coloring}. In this paper, we show that it is NP-complete to determine whether a graph has a local k-coloring for fixed k=4 or k=2t1, where t3. In particular, it is NP-complete to determine whether a planar graph has a local 5-coloring even restricted to the maximum degree =7or8.

The discharging method is most well-known for its central role in the proof of the Four Color Theorem. This proof technique was extensively applied to study various graph coloring problems, in particular on planar graphs. In this paper, we show that suitably altered discharging technique can also be used on domination-type problems. The general discharging approach for domination-type problems is illustrated on a specific domination-type problem, the double Roman domination on some generalized Petersen graphs. By applying this approach, we first prove that $\gamma _{dR}(G) \geq ({3n}/{\Delta (G)+1})$ for any connected graph $G$ with $n\geq 2$ vertices. As examples, we also determine the exact values of the double Roman domination numbers of the generalized Petersen graphs $P(n,1)$ and the double generalized Petersen graphs $DP(n,1)$ . The obtained results imply that $P(n,1)$ is double Roman if and only if $n \not \equiv 2$ (mod 4) and $DP(n,1)$ is double Roman if and only if $n \equiv 0$ (mod 4).

An outer-independent total dominating set (OITDS) of a graph $G$ is a set $D$ of vertices of $G$ such that every vertex of $G$ has a neighbor in $D$ , and the set $V(G)\setminus D$ is independent. The outer-independent total domination number of a graph $G$ , denoted by $\gamma _{oit}(G)$ , is the minimum cardinality of an OITDS of $G$ . An outer-independent total Roman dominating function (OITRDF) on a graph $G$ is a function $f: V(G) \rightarrow \{0, 1, 2\}$ satisfying the conditions that every vertex $u$ with $f(u)=0$ is adjacent to at least one vertex $v$ with $f(v)=2$ , every vertex $x$ with $f(x)\geq 1$ is adjacent to at least one vertex $y$ with $f(y)\geq 1$ , and any two different vertices $a,b$ with $f(a)=f(b)=0$ are not adjacent. The minimum weight $\omega (f) =\sum _{v\in V(G)}f(v)$ of any OITRDF $f$ for $G$ is the outer-independent total Roman domination number of $G$ , denoted by $\gamma _{oitR}(G)$ . A graph $G$ is called an outer-independent total Roman graph (OIT-Roman graph) if $\gamma _{oitR}(G)=2\gamma _{oit}(G)$ . In this paper, we propose dynamic programming algorithms to compute the outer-independent total domination number and the outer-independent total Roman domination number of a tree, respectively. Moreover, we characterize all OIT-Roman graphs and give a linear time algorithm for recognizing an OIT-Roman graph.

A signed Roman k -dominating function on a graph G = ( V ( G ) , E ( G ) ) is a function f : V ( G ) → { − 1 , 1 , 2 } such that (i) every vertex u with f ( u ) = − 1 is adjacent to at least one vertex v with f ( v ) = 2 and (ii) ∑ x ∈ N [ w ] f ( x ) ≥ k holds for any vertex w . The weight of f is ∑ u ∈ V ( G ) f ( u ) , the minimum weight of a signed Roman k -dominating function is the signed Roman k -domination number γ s R k ( G ) of G . It is proved that determining the signed Roman k -domination number of a graph is NP-complete for k ∈ { 1 , 2 } . Using a discharging method, the values γ s R 2 ( C 3 □ C n ) and γ s R 2 ( C 4 □ C n ) are determined for all n .

Let γS′(G) and γSS(G) be the signed edge domination number and signed star domination number of a graph G, respectively. In this paper, we prove that for a tree T of order n≥3, if γS′(T)=γSS(T)=k then k≥(3n+1)/5. Moreover, we prove that for any integer r≥1, there exists a tree Tr on n=5r+3 vertices such that γS′(Tr)=γSS(Tr)=(3n+1)/5.

For a graph $$G=(V, E)$$ , a weak $$\{2\}$$ -dominating function $$f:V\rightarrow \{0,1,2\}$$ has the property that $$\sum _{u\in N(v)}f(u)\ge 2$$ for every vertex $$v\in V$$ with $$f(v)= 0$$ , where N(v) is the set of neighbors of v in G. The weight of a weak $$\{2\}$$ -dominating function f is the sum $$\sum _{v\in V}f(v)$$ and the minimum weight of a weak $$\{2\}$$ -dominating function is the weak $$\{2\}$$ -domination number. In this paper, we introduce a discharging approach and provide a short proof for the lower bound of the weak $$\{2\}$$ -domination number of $$C_n \Box C_5$$ , which was obtained by Stȩpien, et al. (Discrete Appl Math 170:113–116, 2014). Moreover, we obtain the weak $$\{2\}$$ -domination numbers of $$C_n \Box C_3$$ and $$C_n \Box C_4$$ .

Given a positive integer t and a graph F, the goal is to assign a subset of the color set $$\{1,2,\ldots ,t\}$$ to every vertex of F such that every vertex with the empty set assigned has all t colors in its neighborhood. Such an assignment is called the t-rainbow dominating function ( $$t\mathrm{RDF}$$ ) of the graph F. A $$t\mathrm{RDF}$$ is independent ( $$It\mathrm{RDF}$$ ) if vertices assigned with non-empty sets are pairwise non-adjacent. The weight of a $$t\mathrm{RDF}$$ g of a graph F is the value $$w(g) =\sum _{v \in V(F)}|g(v)|$$ . The independent t-rainbow domination number $$i_{rt}(F)$$ is the minimum weight over all $$It\mathrm{RDF}$$ s of F. In this article, it is proved that the independent t-rainbow domination problem is NP-complete even if the input graph is restricted to a bipartite graph or a planar graph, and the results of the study provide some bounds for the independent t-rainbow domination number of any graph for a positive integer t. Moreover, the exact values and bounds of the independent t-rainbow domination numbers of some Petersen graphs and torus graphs are given.

We give a characterization of trees with equal independent domination and secure domination numbers, which answers a question proposed by Merouane and Chellali (2015).We introduce three operations on trees and prove that any tree with equal independent domination and secure domination number can be obtained by these operations. Let i ( G ) and γ s ( G ) be the independent domination number and secure domination number of a graph G, respectively. Merouane and Chellali (2015) 12 proved that i ( T ) ź γ s ( T ) for any tree T and asked to characterize the trees T with i ( T ) = γ s ( T ) . In this paper, we answer the question. We introduce three operations on trees and prove that any tree T with i ( T ) = γ s ( T ) can be obtained by these operations.

A modified stochastic averaging method on single-degree-of-freedom (SDOF) oscillators under white noise excitations with strongly nonlinearity was proposed. Considering the existing approach dealing with strongly nonlinear SDOFs derived by Zhu and Huang [14, 15 ] is quite time consuming in calculating the drift coefficient and diffusion coefficients and the expressions of them are considerable long, the so-called He's energy balance method was applied to overcome the minor defect of the Zhu and Huang's method. The modified method can offer more concise approximate expressions of the drift and diffusion coefficients without weakening the accuracy of predicting the responses of the systems too much by giving an averaged frequency beforehand. Three examples, a cubic and quadratic nonlinearity coexisting oscillator, a quadratic nonlinear oscillator under external white noise excitations and an externally excited Duffing–Rayleigh oscillator, were given to illustrate the approach we proposed. The three examples were excited by the Gaussian white noise and the Gaussian colored noise separately. The stationary responses of probability density of amplitudes and energy, together with joint probability density of displacement and velocity are studied to verify the presented approach. The reliability of the systems were also investigated to offer further support. Digital simulations were carried out and the output of that are coincide with the theoretical approximations well.

An acyclic k-coloring of a graph is a proper vertex k-coloring such that every bichromatic subgraph, induced by this coloring, contains no cycles. A graph is acyclically k-colorable if it has an acyclic k-coloring. In this paper, we prove that every acyclically 4-colorable triangulation with minimum degree more than 3 contains at least four odd-vertices. Moreover, we show that for an acyclically 4-colorable triangulation with minimum degree 4, if it contains exactly four odd-vertices, then the subgraph induced by its four odd-vertices is triangle-free and claw-free. The problem of deciding whether a triangulation is acyclically 4-colorable is NP-complete.Every acyclically 4-colorable triangulation with minimum degree more than 3 contains at least four odd-vertices.For every acyclic 4-colorable 4-connected triangulation with exactly four odd-vertices, it follows that the subgraph induced by the four odd-vertices is triangle-free and claw-free.

A set D ? V ( G ) of a graph G is a dominating set if every vertex v ? V ( G ) is either in D or adjacent to a vertex in D . The domination number γ ( G ) of a graph G is the minimum cardinality of a dominating set of G . Campos and Wakabayashi (2013) and Tokunaga (2013) proved independently that if G is an n -vertex maximal outerplanar graph having t vertices of degree 2, then γ ( G ) ? n + t 4 . We improve their upper bound by showing γ ( G ) ? n + k 4 , where k is the number of pairs of consecutive 2-degree vertices with distance at least 3 on the outer cycle. Moreover, we prove that γ ( G ) ? 5 n 16 for a Hamiltonian maximal planar graph G with n ? 7 vertices.

A new graph parameter, called tree-coritivity, is introduced in this paper. A decycling-cut is a vertex-cut whose removal results in an acyclic graph. Let ω ( G ) be the number of connected components of a graph G. The tree-coritivity of a graph G is the maximum value of ω ( G - S * ) - | S * | , where S * takes over all decycling-cuts of G. It is shown that this parameter can be used to measure the vulnerability of a graph. We prove that the problem of computing the tree-coritivity of a graph is NP-complete. Moreover, we figure out the bounds of tree-coritivity of graphs, give a way to compute the tree-coritivity of the join graph, and determine the exact value of tree-coritivities for some special classes of graphs. A new graph parameter, called tree-coritivity, is introduced.We show that this parameter can be used to measure the vulnerability of a graph.We prove that the problem of computing the tree-coritivity of a graph is NP-complete.We figure out the bounds of tree-coritivity of graphs.We obtain the exact value of tree-coritivities for some special classes of graphs.

It is obtained in this paper by using of discharging method that the adjacent-vertex-distinguishing proper edge chromatic number ? a ' ( G ) ? Δ ( G ) + 1 for any planar bipartite graph G with maximum degree Δ ( G ) = 9 , 10 , or 11 and no component K 2 . This expands a result which belongs to K. Edwards, M. Horňak, M. Wo?niak. The results in this paper expand the results obtained by K. Edwards, M. Horňak, M. Wo?niak. The proof technique in this paper is discharging. The important result, that the adjacent-vertex-distinguishing proper edge chromatic number ? a ' ( G ) ? Δ ( G ) + 1 for any planar bipartite graph G with maximum degree Δ ( G ) = 9 , 10 , or 11, is obtained in this paper.We implicitly give the definitions of K 2 , exceptional vertex, ordinary vertex, and rewrite the abstract.I have read the paper in these two days. The deduction processes in our paper are all right. And the paper is quite readable.

A local k-coloring of a graph G is a function f : V ( G ) ? { 1 , 2 , ? , k } such that for each S ? V ( G ) , 2 ? | S | ? 3 , there exist u , v ? S with | f ( u ) - f ( v ) | at least the size of the subgraph induced by S. The local chromatic number of G is ? ? ( G ) = min ? { k : G has a local k -coloring } . Chartrand et al. 2 asked: does there exist a graph G k such that ? ? ( G k ) = ? ( G k ) = k ? Furthermore, they conjectured that for every positive integer k, there exists a graph G k with ? ? ( G ) = k such that every local k-coloring of G k uses all of the colors 1 , 2 , ? , k . In this paper we give a affirmative answer to the problem and confirm the conjecture. We study the local k-coloring of graphs.We prove that there exists a graph G k such that ? ? ( G k ) = ? ( G k ) = k for any k. This result gives a affirmative answer to a problem proposed by Chartrand et al. 2.We prove that there exists a graph G k with ? ? ( G ) = k such that every local k-coloring of G k uses all of the colors 1 , 2 , ? , k . This result confirms a conjecture proposed by Chartrand et al. 2.

This paper investigates horizontal crossover (HC) and stability-based adaptive inertia weight (SAIW) strategies for comprehensive learning particle swarm optimization. HC applies arithmetic crossover on all the dimensions of two different personal best positions. SAIW adaptively adjusts the inertia weight and acceleration coefficient for each particle on each dimension. Experimental results on various benchmark functions demonstrate that HC can significantly improve the convergence performance for the optimizer, while SAIW cannot. The results also indicate that HC and SAIW need to be further improved.

A subset D of the vertex set of a graph G is a secure dominating set of G if D is a dominating set of G and if, for each vertex u not in D, there is a vertex v in D adjacent to u such that the swap set (D n {v}) ∪ {u} is again a dominating set of G. The secure domination number of G, denoted by γs(G), is the cardinality of a smallest secure dominating set of G. In this paper, we prove that for any tree T on n 3 vertices, n+2/3 γs(T) 2n+2ℓ-t/4 and the bounds are sharp, where ℓ and t are the numbers of leaves and stems of T, respectively. Moreover, we characterize the trees T such that γs(T) = n+2/3.Mathematics Subject Classication (2010): 05C69.Key words: Tree, secure dominating set, secure domination number.

An acyclic $$k$$k-coloring of a graph $$G$$G is a $$k$$k-coloring of its vertices such that no cycle of $$G$$G is bichromatic. $$G$$G is called acyclically $$k$$k-colorable if it admits an acyclic $$k$$k-coloring. In this paper, we prove that the generalized Petersen graph $$P(n,k)$$P(n,k) is acyclically 3-colorable except $$P(4,1)$$P(4,1) and the classical Petersen graph $$P(5,2)$$P(5,2).