Narrow Results

We outline constructions of packet radio networks (with time division multiplexing) that achieve much better parameters than those previously proposed. Given the desired diameter and number of slots per time frame, our networks seek to maximize the possible number of users. We model this as a problem of constructing large graphs or digraphs with given diameter and chromatic index, and relate it to extant work on large graphs with given diameter and maximum degree.

For a given graph G = (V, E), its integrity is defined as I(G) = min_X⊂V {|X|+m(G−X)}, where m(G−X) denote the order of the largest component of G−X. In [9], authors discuss the minimum integrity of tree with given order and the maximum degree. In this paper, we point that the result in [9] is flawed and by elementary method characterize the structure of the minimum integrity tree and thus correct Theorem 4.1 in [9]. Finally, we give the construction method of this kind of extremal graph.

Let $G$ be a connected undirected graph. A vertex coloring $f$ of $G$ is an $N_i$-vertex coloring if for each vertex $x$ in $G$, the number of different colors assigned to $N_G(x)$ is at most $i$. The $N_i$-chromatic number of $G$, denoted by $t_i(G)$, is the maximum number of colors which are used in an $N_i$-vertex coloring of $G$. In this paper, we provide sharp bounds for $t_i(G)$ of a graph $G$ in terms of its vertex cover number, maximum degree and diameter, respectively. We also determine precise values for $t_i(G)$ in some cases.

The distance spectral radius of a connected graph is the largest eigenvalue of its distance matrix. For integers $n$ and $\mathrm{\Delta }$ with $3\le \mathrm{\Delta }\le n-2$, we prove that among the connected graphs on $n$ vertices of given maximum degree $\mathrm{\Delta }$ with at least one cycle, the graph $U(n,\mathrm{\Delta })$ uniquely maximizes the distance spectral radius, where $U(n,\mathrm{\Delta })$ is the graph obtained from the disjoint star on $\mathrm{\Delta }$ vertices and path on $n-\mathrm{\Delta }$ vertices by adding two edges, one connecting the star center with a path end, and the other being a chord of the star.

The inverse sum indeg index of a graph $G$ is defined as $\mathrm{\text{ISI}}(G)={\sum }_{uv\in E(G)}\frac{d(u)d(v)}{d(u)+d(v)}$, where $d(u)$ is the degree of the vertex $u$. In a recent paper, Pattabiraman [Inverse sum indeg index of graphs, AKCE Int. J. Graphs Combinat. 15(2) (2018) 155–167] gave some lower and upper bounds on $\mathrm{\text{ISI}}$ index of all connected graphs in terms of Harmonic index, second Zagreb index and hyper Zagreb index. But some results were erroneous. In this note, we have corrected these results.

The $F$-index of a graph $G$, denoted by $F(G)$, is defined as the sum of weights $d{(u)}^2+d{(v)}^2$ over all edges $uv$ of $G$, where $d(u)$ denotes the degree of a vertex $u$. In this paper, we give sharp upper bounds of the $F$-index (forgotten topological index) over bicyclic graphs, in terms of the order and maximum degree.

The concept of Sombor indices (SO) of a graph was recently introduced by Gutman and the reduced Sombor index ${\mathrm{\text{SO}}}_{\mathrm{\text{red}}}$ of a graph $G$ is defined by ${\mathrm{\text{SO}}}_{\mathrm{\text{red}}}(G)={\sum }_{uv\in E(G)}\sqrt{{(d_G(u)-1)}^2+(d_G{(v)}^2-1)},$ where $d_G(v)$ is the degree of the vertex $v$. In this paper, we study the extremal properties of the reduced Sombor index and characterize the bicyclic graphs with extremal ${\mathrm{\text{SO}}}_{\mathrm{\text{red}}}$-value.

An injective-k coloring of a graph G is a mapping cV(G) → {1, 2, …, k}, such that c(u) ≠ c(v) for each u, v ∈ V(G), whenever u, v have a common neighbor in G. If G has an injective-k coloring, then we call that G is injective-k colorable. Call χ_i(G) = min{k | G is injective-k colorable} is the injective chromatic number of G. Assign each vertex v ∈ V(G) a coloring set L(v), then L = {L(v) | v ∈ V(G)} is said to be a color list of G. Let L be a color list of G, if G has an injective coloring c such that c(v) ∈ L(v), ∀v ∈ V(G), then we call c an injective L-coloring of G. If for any color list L, such that |L(v)| ≥ k, G has an injective L-coloring, then G is said to be injective k-choosable. Call is injective k-choosable} is the injective chromatic number of G. So far, for the plane graph G of girth g(G) ≥ 5 and maximum degree Δ(G) ≥ 8, the best result of injective chromatic number is χ_i(G) ≤ Δ + 8. In this paper, for the plane graph G, we proved that if girth g(G) ≥ 5 and maximum degree Δ(G) ≥ 8.

A plane graph G is entirely k-choosable if, for every list L of colors satisfying L(x) = k for x ∈ V(G) ∪ E(G) ∪ F(G), there exists a coloring which assigns to each vertex, each edge and each face a color from its list so that any adjacent or incident elements receive different colors. In this paper, we show that every plane graph G with maximum degree Δ ≤ 5 is entirely (Δ + 5)-choosable.

We study the list 2-distance coloring of a graph G, and its maximum average degree, denoted mad(G). For Δ(G) = 5, we proved that , , and ch₂(G) ≤ 11 if mad(G) < 3 respectively, where ch₂(G) is the list 2-distance chromatic number.

A 2-distance coloring of $G$ is a function $\phi$: $V(G)\to \{1,2,\dots ,k\}$, such that for every two distinct vertices $u$, $v$ in $G$, $\phi (u)\ne \phi (v)$ if $0<d_G(u,v)\le 2$. The 2-distance chromatic number of $G$ is the least integer $k$ such that $G$ has a $k$-$2$-distance coloring, denoted by ${\chi }_2(G)$. Similarly, the list 2-distance chromatic number of $G$ is denoted by ${\chi }_2^l(G)$. In this paper, we proved that: (1) for every planar graph with $g(G)\ge 5$ and $\mathrm{\Delta }(G)\ge 12$, ${\chi }_2^l(G)\le \mathrm{\Delta }(G)+6$; (2) for every planar graph with $g(G)\ge 6$ and $\mathrm{\Delta }(G)\ge 9$, ${\chi }_2^l(G)\le \mathrm{\Delta }(G)+3$.

It was proved in [Y. Bu and C. Shang, List 2-distance coloring of planar graphs without short cycles, Discrete Math. Algorithm. Appl.8 (2016) 1650013] that for every planar graph with girth $g\ge 5$ and maximum degree $\mathrm{\Delta }\ge 12$ is list 2-distance $(\mathrm{\Delta }+6)$-colorable. In this paper, we proved that: for every planar graph with $g\ge 5$ and $\mathrm{\Delta }\ge 30$ is list 2-distance $(\mathrm{\Delta }+5)$-colorable.

The independence number of a graph $G$, denoted by $\alpha (G)$, is the maximum cardinality of an independent set of vertices in $G$. [Henning and Löwenstein An improved lower bound on the independence number of a graph, Discrete Applied Mathematics 179 (2014) 120–128.] proved that if a connected graph $G$ of order $n$ and size $m$ does not belong to a specific family of graphs, then $\alpha (G)>\frac{2}{3}n-\frac{1}{4}m$. In this paper, we strengthen the above bound for connected graphs with maximum degree at least three that have a non-cut-vertex of maximum degree. We show that if a connected graph $G$ of order $n$ and size $m$ has a non-cut-vertex of maximum degree then $\alpha (G)\ge \frac{2}{3}n-\frac{1}{4}(m-\mathrm{\Delta }(G))-\frac{11}{12}$, where $\mathrm{\Delta }(G)$ is the maximum degree of the vertices of $G$. We also characterize all connected graphs $G$ of order $n$ and size $m$ that have a non-cut-vertex of maximum degree and $\alpha (G)\le \frac{2}{3}n-\frac{1}{4}(m-\mathrm{\Delta }(G))-\frac{2}{3}$.

Regarding the 2-$distance$ coloring of planar graphs, in 1977, Wegner conjectured that for a graph $G$: (1) ${\chi }_2(G)\le 7$ if $\mathrm{\Delta }(G)=3$. (2) ${\chi }_2(G)\le \mathrm{\Delta }(G)+5$ if $4\le \mathrm{\Delta }(G)\le 7$. (3) ${\chi }_2(G)\le \lfloor \frac{3}{2}\mathrm{\Delta }(G)\rfloor +1$ if $\mathrm{\Delta }(G)\ge 8$. In this paper, we proved that for every planar graph with maximum degree $\mathrm{\Delta }(G)\le 4$: (1) ${\chi }_2^l(G)\le 10$ if $g(G)\ge 6$. (2) ${\chi }_2^l(G)\le 7$ if $g(G)\ge 10$.

The linear 2-arboricity la${}_2(G)$ of a graph $G$ is the least integer $k$ such that $G$ can be partitioned into $k$ edge-disjoint forests, whose component trees are paths of length at most 2. In this paper, we prove that if $G$ is a 1-planar graph without 3-cycles and with maximum degree $\mathrm{\Delta }$, then la${}_2(G)\le \lceil \frac{\mathrm{\Delta }+1}{2}\rceil +6$.

A $k$-$injective$-$edge$-$coloring$$of$$a$$graph$$G$ is a mapping $f:E(G)\to \{1,2,\dots ,k\}$ such that $f(e_1)\ne f(e_3)$ for any three consecutive edges $e_1$,$e_2$,$e_3$ of a path or a $3$-cycle. ${\chi }_i^{\prime }(G)=min\{k|$$G$ has a $k$-injective-edge-coloring$\}$ is called the injective chromatic index of G. In this paper, we prove that for planar graphs $G$ with $\mathrm{\Delta }(G)\ge 6$, (1)${\chi }_i^{\prime }(G)\le 3\mathrm{\Delta }(G)-3$ if $g(G)\ge 6$; (2)${\chi }_i^{\prime }(G)\le 3\mathrm{\Delta }(G)-4$ if $g(G)\ge 7$.

A proper subset $X$ of vertices in the graph $G$ is a captive dominating set if it is a total dominating set and each vertex in $X$ dominates at least one vertex which does not belong to $X$; also, the captive domination number of $G$, denoted by ${\gamma }_{\mathrm{\text{ca}}}(G)$, is the cardinality of a minimum captive dominating set of $G$. In [M. N. Al-Harere, A. A. Omran and A. T. Breesam, Captive domination in graphs, Discrete Math. Algorithms Appl. 12(6) (2020) 2050076], Al-Harere et al., presented some lower and upper bounds for the captive domination number of $G$, using the number of vertices and edges. Here, we present some upper bounds for ${\gamma }_{\mathrm{\text{ca}}}(G)$, using independence number and clique number. Also, the captive domination number of split graphs is studied. Among other results, some lower bounds for the captive domination number, in terms of maximum degree and the number of vertices with maximum degree, are presented.