d-strong Edge Colorings of Graphs

For a proper edge coloring of a graph G the palette S(v) of a vertex v is the set of the colors of the incident edges. If S(u) ≠ S(v) then the two vertices u and v of G are distinguished by the coloring. A d-strong edge coloring of G is a proper edge coloring that distinguishes all pairs of vertices u and v with distance 1 ≤ d (u, v) ≤ d. The d-strong chromatic index ${\chi_{d}^{\prime}(G)}$ of G is the minimum number of colors of a d-strong edge coloring of G. Such colorings generalize strong edge colorings and adjacent strong edge colorings as well. We prove some general bounds for ${\chi_{d}^{\prime}(G)}$ , determine ${\chi_{d}^{\prime}(G)}$ completely for paths and give exact values for cycles disproving a general conjecture of Zhang et al. (Acta Math Sinica Chin Ser 49:703–708 2006)).     

Degree Sum Conditions for Cyclability in Bipartite Graphs

We denote by G[X, Y] a bipartite graph G with partite sets X and Y. Let d _G (v) be the degree of a vertex v in a graph G. For G[X, Y] and ${S \subseteq V(G),}$ we define ${\sigma_{1,1}(S):=\min\{d_G(x)+d_G(y) : (x,y) \in (X \cap S,Y) \cup (X, Y \cap S), xy \not\in E(G)\}}$ . Amar et al. (Opusc. Math. 29:345–364, 2009) obtained σ _1,1(S) condition for cyclability of balanced bipartite graphs. In this paper, we generalize the result as it includes the case of unbalanced bipartite graphs: if G[X, Y] is a 2-connected bipartite graph with |X| ≥ |Y| and ${S \subseteq V(G)}$ such that σ _1,1(S) ≥ |X| + 1, then either there exists a cycle containing S or ${|S \cap X| > |Y|}$ and there exists a cycle containing Y. This degree sum condition is sharp.     

On the Broadcast Independence Number of Grid Graph

A broadcast on a nontrivial connected graph G is a function ${f:V \longrightarrow \{0, \ldots,\operatorname{diam}(G)\}}$ such that for every vertex ${v \in V(G)}$ , ${f(v) \leq e(v)}$ , where ${\operatorname{diam}(G)}$ denotes the diameter of G and e(v) denotes the eccentricity of vertex v. The broadcast independence number is the maximum value of ${\sum_{v \in V} f(v)}$ over all broadcasts f that satisfy ${d(u,v) > \max \{f(u), f(v)\}}$ for every pair of distinct vertices u, v with positive values. We determine this invariant for grid graphs ${G_{m,n} = P_m \square P_n}$ , where ${2 \leq m \leq n}$ and □ denotes the Cartesian product. We hereby answer one of the open problems raised by Dunbar et al. in (Discrete Appl Math 154:59–75, 2006).     

The {k}-domatic number of a graph

For a positive integer k, a {k}-dominating function of a graph G is a function f from the vertex set V(G) to the set {0, 1, 2, . . . , k} such that for any vertex ${v\in V(G)}$ , the condition ${\sum_{u\in N[v]}f(u)\ge k}$ is fulfilled, where N[v] is the closed neighborhood of v. A {1}-dominating function is the same as ordinary domination. A set {f ₁, f ₂, . . . , f _d } of {k}-dominating functions on G with the property that ${\sum_{i=1}^df_i(v)\le k}$ for each ${v\in V(G)}$ , is called a {k}-dominating family (of functions) on G. The maximum number of functions in a {k}-dominating family on G is the {k}-domatic number of G, denoted by d _{k}(G). Note that d _{1}(G) is the classical domatic number d(G). In this paper we initiate the study of the {k}-domatic number in graphs and we present some bounds for d _{k}(G). Many of the known bounds of d(G) are immediate consequences of our results.     

On Spanning Disjoint Paths in Line Graphs

Spanning connectivity of graphs has been intensively investigated in the study of interconnection networks (Hsu and Lin, Graph Theory and Interconnection Networks, 2009). For a graph G and an integer s > 0 and for ${u, v \in V(G)}$ with u ≠ v, an (s; u, v)-path-system of G is a subgraph H consisting of s internally disjoint (u,v)-paths. A graph G is spanning s-connected if for any ${u, v \in V(G)}$ with u ≠ v, G has a spanning (s; u, v)-path-system. The spanning connectivity κ*(G) of a graph G is the largest integer s such that G has a spanning (k; u, v)-path-system, for any integer k with 1 ≤ k ≤ s, and for any ${u, v \in V(G)}$ with u ≠ v. An edge counter-part of κ*(G), defined as the supereulerian width of a graph G, has been investigated in Chen et al. (Supereulerian graphs with width s and s-collapsible graphs, 2012). In Catlin and Lai (Graph Theory, Combinatorics, and Applications, vol. 1, pp. 207–222, 1991) proved that if a graph G has 2 edge-disjoint spanning trees, and if L(G) is the line graph of G, then κ*(L(G)) ≥ 2 if and only if κ(L(G)) ≥ 3. In this paper, we extend this result and prove that for any integer k ≥ 2, if G ₀, the core of G, has k edge-disjoint spanning trees, then κ*(L(G)) ≥ k if and only if κ(L(G)) ≥ max{3, k}.     

Roman Domination Dot-critical Graphs

A Roman dominating function on a graph G is a function f : V(G) → {0, 1, 2} satisfying the condition that every vertex u for which f (u) = 0 is adjacent to at least one vertex v for which f (v) = 2. The weight of a Roman dominating function is the value ${f(V(G))=\sum_{u \in V(G)}f(u)}$ . The Roman domination number, γ _R (G), of G is the minimum weight of a Roman dominating function on G. In this paper, we study graphs for which contracting any edge decreases the Roman domination number.     

On the Lucky Choice Number of Graphs

Suppose that G is a graph and ${f: V (G) \rightarrow \mathbb{N}}$ is a labeling of the vertices of G. Let S(v) denote the sum of labels over all neighbors of the vertex v in G. A labeling f of G is called lucky if ${S(u) \neq S(v),}$ for every pair of adjacent vertices u and v. Also, for each vertex ${v \in V(G),}$ let L(v) denote a list of natural numbers available at v. A list lucky labeling, is a lucky labeling f such that ${f(v) \in L(v),}$ for each ${v \in V(G).}$ A graph G is said to be lucky k-choosable if every k-list assignment of natural numbers to the vertices of G permits a list lucky labeling of G. The lucky choice number of G, η _l (G), is the minimum natural number k such that G is lucky k-choosable. In this paper, we prove that for every graph G with ${\Delta \geq 2, \eta_{l}(G) \leq \Delta^2-\Delta + 1,}$ where Δ denotes the maximum degree of G. Among other results we show that for every 3-list assignment to the vertices of a forest, there is a list lucky labeling which is a proper vertex coloring too.     

On Eccentric Connectivity Index of Eccentric Graph of Regular Dendrimer

The eccentric connectivity index \(\xi ^c(G)\) of a connected graph G is defined as \(\xi ^c(G) =\sum _{v \in V(G)}{deg(v) e(v)},\) where deg(v) is the degree of vertex v and e(v) is the eccentricity of v. The eccentric graph, \(G_e\), of a graph G has the same set of vertices as G,  with two vertices u, v adjacent in \(G_e\) if and only if either u is an eccentric vertex of v or v is an eccentric vertex of u. In this paper, we obtain a formula for the eccentric connectivity index of the eccentric graph of a regular dendrimer. We also derive a formula for the eccentric connectivity index for the second iteration of eccentric graph of regular dendrimer.     

Fractional f-Edge Cover Chromatic Index of Graphs

Let G be a graph, and let f be an integer function on V with ${1\leq f(v)\leq d(v)}$ to each vertex ${\upsilon \in V}$ . An f-edge cover coloring is a coloring of edges of E(G) such that each color appears at each vertex ${\upsilon \in V(G)}$ at least f(υ) times. The maximum number of colors needed to f-edge cover color G is called the f-edge cover chromatic index of G and denoted by ${\chi^{'}_{fc}(G)}$ . It is well known that any simple graph G has the f-edge cover chromatic index equal to δ _f (G) or δ _f (G) ? 1, where ${\delta_{f}(G)=\,min\{\lfloor \frac{d(v)}{f(v)} \rfloor: v\in V(G)\}}$ . The fractional f-edge cover chromatic index of a graph G, denoted by ${\chi^{'}_{fcf}(G)}$ , is the fractional f-matching number of the edge f-edge cover hypergraph ${\mathcal{H}}$ of G whose vertices are the edges of G and whose hyperedges are the f-edge covers of G. In this paper, we give an exact formula of ${\chi^{'}_{fcf}(G)}$ for any graph G, that is, ${\chi^{'}_{fcf}(G)=\,min \{\min\limits_{v\in V(G)}d_{f}(v), \lambda_{f}(G)\}}$ , where ${\lambda_{f}(G)=\min\limits_{S} \frac{|C[S]|}{\lceil (\sum\limits_{v\in S}{f(v)})/2 \rceil}}$ and the minimum is taken over all nonempty subsets S of V(G) and C[S] is the set of edges that have at least one end in S.     

Upper bounds on the signed (k, k)-domatic number

Let G be a graph with vertex set V(G), and let f : V(G) → {?1, 1} be a two-valued function. If k ≥ 1 is an integer and ${\sum_{x\in N[v]} f(x) \ge k}$ for each ${v \in V(G)}$ , where N[v] is the closed neighborhood of v, then f is a signed k-dominating function on G. A set {f ₁,f ₂, . . . ,f _d } of distinct signed k-dominating functions on G with the property that ${\sum_{i=1}^d f_i(x) \le k}$ for each ${x \in V(G)}$ , is called a signed (k, k)-dominating family (of functions) on G. The maximum number of functions in a signed (k, k)-dominating family on G is the signed (k, k)-domatic number of G. In this article we mainly present upper bounds on the signed (k, k)-domatic number, in particular for regular graphs.     

Optimal channel assignment and <Emphasis Type="Italic">L</Emphasis>(<Emphasis Type="Italic">p</Emphasis>, 1)-labeling

The optimal channel assignment is an important optimization problem with applications in optical networks. This problem was formulated to the L(p, 1)-labeling of graphs by Griggs and Yeh (SIAM J Discrete Math 5:586–595, 1992). A k-L(p, 1)-labeling of a graph G is a function \(f:V(G)\rightarrow \{0,1,2,\ldots ,k\}\) such that \(|f(u)-f(v)|\ge p\) if \(d(u,v)=1\) and \(|f(u)-f(v)|\ge 1\) if \(d(u,v)=2\), where d(u, v) is the distance between the two vertices u and v in the graph. Denote \(\lambda _{p,1}^l(G)= \min \{k \mid G\) has a list k-L(p, 1)-labeling\(\}\). In this paper we show upper bounds \(\lambda _{1,1}^l(G)\le \Delta +9\) and \(\lambda _{2,1}^l(G)\le \max \{\Delta +15,29\}\) for planar graphs G without 4- and 6-cycles, where \(\Delta \) is the maximum vertex degree of G. Our proofs are constructive, which can be turned to a labeling (channel assignment) method to reach the upper bounds.     

The atom-bond connectivity index of chemical bicyclic graphs

The atom-bond connectivity (ABC) index provides a good model for the stabilityof linear and branched alkanes as well as the strain energy of cycloalkanes,which is defined as ABC(G) =Σuv∈(G)√ du +dv - 2...     

Collapsible Graphs and Hamiltonicity of Line Graphs

Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai (Combinatorics and Graph Theory, vol 95, World Scientific, Singapore, pp 53–69; Conjecture 8.6 of 1995) conjectured that every 3-edge connected and essentially 6-edge connected graph is collapsible. Denote D ₃(G) the set of vertices of degree 3 of graph G. For ${e = uv \in E(G)}$ , define d(e) = d(u) + d(v) ? 2 the edge degree of e, and ${\xi(G) = \min\{d(e) : e \in E(G)\}}$ . Denote by λ ^m (G) the m-restricted edge-connectivity of G. In this paper, we prove that a 3-edge-connected graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq7}$ is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq6}$ is collapsible; a 3-edge-connected graph with ${\xi(G)\geq6}$ , ${\lambda^2(G)\geq4}$ , and ${\lambda^3(G)\geq6}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq6}$ , and ${\lambda^3(G)\geq5}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected graph with ${\xi(G)\geq5}$ , and ${\lambda^2(G)\geq4}$ with at most 9 vertices of degree 3 is collapsible. As a corollary, we show that a 4-connected line graph L(G) with minimum degree at least 5 and ${|D_3(G)|\leq9}$ is Hamiltonian.     

Some sufficient conditions for Hamiltonian property in terms of Wiener-type invariants

The Wiener-type invariants of a simple connected graph G = (V, E) can be expressed in terms of the quantities \(W_{f}=\sum_{\{u,v\}\subseteq V}f(d_{G}(u,v))\) for various choices of the function f(x), where d_G(u,v) is the distance between vertices u and v in G. In this paper, we give some sufficient conditions for a connected graph to be Hamiltonian, a connected graph to be traceable, and a connected bipartite graph to be Hamiltonian in terms of the Wiener-type invariants.     

The Signed k-Submatchings in Graphs

A signed k-submatching of a graph G is a function f : E(G) → {?1,1} satisfying f (E _G (v)) ≤ 1 for at least k vertices ${v \in V(G)}$ . The maximum of the values of f (E(G)), taken over all signed k-submatchings f, is called the signed k-submatching number and is denoted by ${\beta_S^{k}(G)}$ . In this paper, sharp bounds on ${\beta_S^{k}(G)}$ for general graphs are presented. Exact values of ${\beta_S^{k}(G)}$ for several classes of graphs are found.     

Signed total (k, k)-domatic number of digraphs

Let D be a finite and simple digraph with vertex set V(D), and let f: V(D) → {?1, 1} be a two-valued function. If k ≥?1 is an integer and ${\sum_{x \in N^-(v)}f(x) \ge k}$ for each ${v \in V(G)}$ , where N ^?(v) consists of all vertices of D from which arcs go into v, then f is a signed total k-dominating function on D. A set {f ₁, f ₂, . . . , f _d } of signed total k-dominating functions on D with the property that ${\sum_{i=1}^df_i(x)\le k}$ for each ${x \in V(D)}$ , is called a signed total (k, k)-dominating family (of functions) on D. The maximum number of functions in a signed total (k, k)-dominating family on D is the signed total (k, k)-domatic number on D, denoted by ${d_{st}^{k}(D)}$ . In this paper we initiate the study of the signed total (k, k)-domatic number of digraphs, and we present different bounds on ${d_{st}^{k}(D)}$ . Some of our results are extensions of known properties of the signed total domatic number ${d_{st}(D)=d_{st}^{1}(D)}$ of digraphs D as well as the signed total domatic number d _st (G) of graphs G, given by Henning (Ars Combin. 79:277–288, 2006).     

The Chvátal–Erdös Condition for Group Connectivity in Graphs

Let G be a graph and A an abelian group with the identity element 0 and ${|A| \geq 4}$ . Let D be an orientation of G. The boundary of a function ${f: E(G) \rightarrow A}$ is the function ${\partial f: V(G) \rightarrow A}$ given by ${\partial f(v) = \sum_{e \in E^+(v)}f(e) - \sum_{e \in E^-(v)}f(e)}$ , where ${v \in V(G), E^+(v)}$ is the set of edges with tail at v and ${E^-(v)}$ is the set of edges with head at v. A graph G is A-connected if for every b: V(G) → A with ${\sum_{v \in V(G)} b(v) = 0}$ , there is a function ${f: E(G) \mapsto A-\{0\}}$ such that ${\partial f = b}$ . A graph G is A-reduced to G′ if G′ can be obtained from G by contracting A-connected subgraphs until no such subgraph left. Denote by ${\kappa^{\prime}(G)}$ and α(G) the edge connectivity and the independent number of G, respectively. In this paper, we prove that for a 2-edge-connected simple graph G, if ${\kappa^{\prime}(G) \geq \alpha(G)-1}$ , then G is A-connected or G can be A-reduced to one of the five specified graphs or G is one of the 13 specified graphs.     

On Group Choosability of Graphs,II

Given a group A and a directed graph G, let F(G, A) denote the set of all maps ${f : E(G) \rightarrow A}$ . Fix an orientation of G and a list assignment ${L : V(G) \mapsto 2^A}$ . For an ${f \in F(G, A)}$ , G is (A, L, f)-colorable if there exists a map ${c:V(G) \mapsto \cup_{v \in V(G)}L(v)}$ such that ${c(v) \in L(v)}$ , ${\forall v \in V(G)}$ and ${c(x)-c(y)\neq f(xy)}$ for every edge e = xy directed from x to y. If for any ${f\in F(G,A)}$ , G has an (A, L, f)-coloring, then G is (A, L)-colorable. If G is (A, L)-colorable for any group A of order at least k and for any k-list assignment ${L:V(G) \rightarrow 2^A}$ , then G is k-group choosable. The group choice number, denoted by ${\chi_{gl}(G)}$ , is the minimum k such that G is k-group choosable. In this paper, we prove that every planar graph is 5-group choosable, and every planar graph with girth at least 5 is 3-group choosable. We also consider extensions of these results to graphs that do not have a K ₅ or a K _3,3 as a minor, and discuss group choosability versions of Hadwiger’s and Woodall’s conjectures.     

The Number of Independent Sets in a Graph with Small Maximum Degree

Let ind(G) be the number of independent sets in a graph G. We show that if G has maximum degree at most 5 then

Closure and Spanning k-Trees

In this paper, we propose a new closure concept for spanning k-trees. A k-tree is a tree with maximum degree at most k. We prove that: Let G be a connected graph and let u and v be nonadjacent vertices of G. Suppose that \({\sum_{w \in S}d_G(w) \geq |V(G)| -1}\) for every independent set S in G of order k with \({u,v \in S}\) . Then G has a spanning k-tree if and only if G + uv has a spanning k-tree. This result implies Win’s result (Abh Math Sem Univ Hamburg, 43:263–267, 1975) and Kano and Kishimoto’s result (Graph Comb, 2013) as corollaries.