Search

A proper k-edge coloring of a graph G is an assignment of one of k colors to each edge of G such that there are no two edges with the same color incident to a common vertex. Let f (v)denote the sum of colors of the edges incident to v. A k-neighbor sum distinguishing edge coloring of G is a proper k-edge coloring of G such that for each edge uv ∈ E(G), f (u) ≠ f (v). By $${\chi^\prime_{\sum} }(G)$$ , we denote the smallest value k in such a coloring of G. Letmad(G) denote the maximum average degree of a graph G. In this paper, we prove that every normal graph with mad $$(G) < \tfrac{{10}}{3}$$ and Δ(G) ≥ 8 admits a(Δ(G) + 2)-neighbor sum distinguishing edge coloring. Our approach is based on the Combinatorial Nullstellensatz and discharging method.

Let G be a graph and let its maximum degree and maximum average degree be denoted by Δ(G) and mad(G), respectively. A neighbor sum distinguishing k-edge colorings of graph G is a proper k-edge coloring of graph G such that, for any edge uv ∈ E(G), the sum of colors assigned on incident edges of u is different from the sum of colors assigned on incident edges of v. The smallest value of k in such a coloring of G is denoted by χ′∑(G). Flandrin et al. proposed the following conjecture that χ′∑ (G) ≤ Δ(G) + 2 for any connected graph with at least 3 vertices and G ≠ C5. In this paper, we prove that the conjecture holds for a normal graph with mad(G) < $$\tfrac{{37}} {{12}}$$ and Δ(G) ≥ 7.

Natural disasters occur frequently in recent years, causing huge casualties and property losses. Nowadays, people pay more and more attention to the emergency logistics problems. This paper studies the emergency logistics problem with multi-center, multi-commodity, and single-affected-point. Considering that the path near the disaster point may be damaged, the information of the state of the paths is not complete, and the travel time is uncertainty, we establish the nonlinear programming model that objective function is the maximization of time-satisfaction degree. To overcome these drawbacks: the incomplete information and uncertain time, this paper firstly evaluates the multiple roads of transportation network based on grey theory and selects the reliable and optimal path. Then simplify the original model under the scenario that the vehicle only follows the optimal path from the emergency logistics center to the affected point, and use Lingo software to solve it. The numerical experiments are presented to show the feasibility and effectiveness of the proposed method.