Narrow Results

A vertex subset $S$ of a graph $G$ is a $k$-path vertex cover if $S$ intersects any $k$-path in $G,$ for some positive integer $k.$ The minimum magnitude of all $k$-path vertex covers is called $k$-path vertex cover number of $G$ (denoted ${\psi }_k(G)$). In this contribution, we gave estimations of ${\psi }_k(C_m\square P_n^2),$${\psi }_k(C_m\square S_{n+1})$ and the exact values of ${\psi }_3(P_m\square C_n),$${\psi }_3(C_m\square S_{n+1})$ and ${\psi }_k(P_m\square S_{n+1})$. We also obtain the ${\psi }_k(G)$ when $G$ is the Cartesian product of complete and complete bipartite graph.

For each commutative ring $R$ we associate a simple graph ${\mathrm{\Gamma }}_1^{\ast }(R)$. We investigate the properties of an Artinian ring $R$ when ${\mathrm{\Gamma }}_1^{\ast }(R)$ is a star.

Traditional fault tolerability is regularly measured by classical vertex or edge connectivity. Menger’s theorem shows that the number of (edge)-disjoint paths is closely related to (edge) connectivity. Clearly, disjoint paths not only provide alternative routings to tolerate faulty vertices but also avoid communication bottlenecks. Furthermore, disjoint paths can speed up the transmission time by distributing data among disjoint paths. In order to assess the fault tolerance of the network objectively, we aim to extend vertex or edge failures to substructure malfunction. In this paper, we show the maximum number of vertex (edge)-disjoint paths in star graph in the case of genetic substructure faults. Let $S_k$ ($1\le k\le n-1$) be a $k$-dimensional substar of $S_n$. We show that there exist $min\{d_{S_n-S_k}(u),d_{S_n-S_k}(v)\}$ vertex (edge)-disjoint paths to connect any two vertices $u$ and $v$ in $S_n-S_k$, where $d_{S_n-S_k}(u)$ is the degree of vertex $u$ in $S_n-S_k$. In addition, we show that (edge) connectivity and $1$-extra connectivity of $S_n-S_k$ are $n-2$, $2n-5$, respectively.

The capability of fault tolerance is one of the advantages of multiprocessor systems. In this paper, we prove that the fault tolerance of an n-star graph is 2n-5 with restriction to the forbidden faulty set. And we propose an algorithm for examining the connectivity of an n-star graph when there exist at most 2n - 4 faults. The algorithm requires O(n²log n) time. Besides, we improve the fault-tolerant routing algorithm proposed by Bagherzadeh et al. by calculating the cycle structure of a permutation and the avoidance of routing message to a node without any nonfaulty neighbor. This calculation needs only constant time. And then, we propose an efficient fault-tolerant broadcasting algorithm. When there is no fault, our broadcasting algorithm remains optimal. The penalty is O(n) if there exists only one fault, and the penalty is O(n²) if there exist at most n - 2 faults.

This paper introduces the penmutational graph, a new network topology, which preserves the same desirable properties as those of a star graph topology. A permutational graph can be decomposed into subgraphs induced by node sets defined by equivalence classes. Using this decomposition, its structual properties as well as the relationship among graph families, permutational graphs, star graphs, and complete graphs are studied. Moreover, the diameters of permutational graphs are investigated and good estimates are obtained which are better than those of some network topologies of similar orders.

We take advantage of the hierarchical structure of the star graph network to obtain an efficient method for constructing node-disjoint paths between arbitrary pairs of nodes in the network. A distributed fault-tolerant routing algorithm for the star network based on this construction method is then presented and evaluated. The proposed algorithm adapts the routing decisions in response to node failures. Node failure and repair conditions may arise dynamically (at any time) provided that the total number of faulty nodes at any given time is less than the node-connectivity n - 1 of the n-star. When a message is blocked due to faulty components, the source of the message is warned and requested to switch to a different node-disjoint path. The methods used to identify the paths, to propagate failure information back to source nodes, and to switch from a routing path to another incur little communication and computation overhead. We show that if the node failures occur 'reasonably' apart in time, then all messages will be routed on paths of length δ + ε where δ is the minimum distance between the source and the destination and ε is 0, 2, or 4. In the unlikely case where more failures occur in a 'short period', the algorithm still delivers all messages but via possibly longer paths.

In this paper, we consider the problem of constructing a multicast tree in star interconnection networks under the single-port communication model. Unlike previous schemes for constructing space-efficient multicast trees, we adopt the completion time of each multicast as the objective function to be minimized. In particular, we study a special case of the problem in which all destination vertices are immediate neighbors of the source vertex, and propose a multicast scheme of time units for the star graph of dimension n.

The diagnosis of faulty processors plays an important role in multiprocessor systems for reliable computing, and the diagnosability of many well-known networks has been explored. Zheng et al. showed that the diagnosability of the n-dimensional star graph S_n is n - 1. Lai et al. introduced a restricted diagnosability of multiprocessor systems called conditional diagnosability. They consider the situation when no faulty set can contain all the neighbors of any vertex in the system. In this paper, we study the conditional diagnosability of Cayley graphs generated by transposition trees (which include the star graphs) under the comparison model, and show that it is 3n - 8 for n ≥ 4, except for the n-dimensional star graph, for which it is 3n - 7. Hence the conditional diagnosability of these graphs is about three times larger than their classical diagnosability.

The local connectivity of two vertices is defined as the maximum number of internally vertex-disjoint paths between them. In this paper, we define two vertices as maximally local-connected, if the maximum number of internally vertex-disjoint paths between them equals the minimum degree of these two vertices. Moreover, we show that an (n-1)-regular Cayley graph generated by transposition tree is maximally local-connected, even if there are at most (n-3) faulty vertices in it, and prove that it is also (n-1)-fault-tolerant one-to-many maximally local-connected.

A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least one vertex in each other color classes. The b-chromatic number of a graph G, denoted by $\phi \left(G\right)$, is the maximal integer k such that G has a b-coloring with k colors. In this paper, the b-chromatic numbers of the coronas of cycles, star graphs and wheel graphs with different numbers of vertices, respectively, are obtained. Also the bounds for the b-chromatic number of corona of any two graphs is discussed.

Let $R$ be a commutative ring with identity and $𝔸(R)$ be the set of ideals of $R$ with nonzero annihilator. The annihilator-ideal graph of $R$, denoted by $A_I(R)$, is a simple graph with the vertex set $𝔸{(R)}^{\ast }:=𝔸(R)\backslash \{(0)\}$, and two distinct vertices $I$ and $J$ are adjacent if and only if ${\mathrm{\text{Ann}}}_R(IJ)\ne {\mathrm{\text{Ann}}}_R(I)\cup {\mathrm{\text{Ann}}}_R(J)$. In this paper, we study the affinity between the annihilator-ideal graph and the annihilating-ideal graph $𝔸𝔾(R)$ (a well known graph with the same vertices and two distinct vertices $I,J$ are adjacent if and only if $IJ=0$) associated with $R$. All rings whose $A_I(R)\ne 𝔸𝔾(R)$ and $\mathrm{\text{gr}}(A_I(R))=4$ are characterized. Among other results, we obtain necessary and sufficient conditions under which $A_I(R)$ is a star graph.

We prove that the spectrum of a Cayley graph over a finite group with a normal generating set S containing with every its element s all generators of the cyclic group 〈s〉 is integral. In particular, a Cayley graph of a 2-group generated by a normal set of involutions is integral. We prove that a Cayley graph over the symmetric group of degree n no less than 2 generated by all transpositions is integral. We find the spectrum of a Cayley graph over the alternating group of degree n no less than 4 with a generating set of 3-cycles of the form (k i j) with fixed k, as {−n+1, 1−n+1, 2² −n+1, …, (n−1)² −n+1}.

A graph $G$ with $p$ vertices and $q$ edges has antimagic labeling if there is a bijection from the edge set of the graph to the label set $\{1,2,\dots ,q\}$ such that $p$ vertices must have distinct vertex sums, where the vertex sums are determined by adding up all the edge labels incident to each vertex $v$ in $V(G)$. Hartsfield and Ringel conjectured that every connected graph is antimagic, except $P_2$. In this study, we identified a class of connected graphs that lend credence to this conjecture. In this paper, we proved that the tensor product of a Wheel Graph, Helm Graph, and Flower graph with Star is antimagic.

For a connected graph G, a vertex subset F ⊂ V(G) is a cyclic vertex-cut of G if G - F is disconnected and at least two of its components contain cycles. The cardinality of a minimum cyclic vertex-cut of G, denoted by κ_c(G), is the cyclic vertex-connectivity of G. In this paper, we show that for any integer n ≥ 4, the n-dimensional star graph SG_n has κ_c(SG_n) = 6(n - 3).

Let $R$ be a commutative ring with identity and $A(R)$ be the set of ideals with nonzero annihilator. The strongly annihilating-ideal graph of $R$ is defined as the graph $\mathrm{\text{SAG}}(R)$ with the vertex set $A{(R)}^{\ast }=A(R)\backslash \{0\}$ and two distinct vertices $I$ and $J$ are adjacent if and only if $I\cap \mathrm{\text{Ann}}(J)\ne (0)$ and $J\cap \mathrm{\text{Ann}}(I)\ne (0)$. It is proved that $\mathrm{\text{SAG}}(R)$ is connected with diameter at most two and with girth at most four, if it contains a cycle. Moreover, we characterize all rings whose strongly annihilating-ideal graphs are complete or star. Furthermore, we study the affinity between strongly annihilating-ideal graph and annihilating-ideal graph (a well-known graph with the same vertices and two distinct vertices $I,J$ are adjacent if and only if $IJ=0$) associated with a commutative ring.

In this paper, we obtain explicitly the $r$-dynamic chromatic number of the direct product of a path $P_m$ with a $k$-subdivision $S_n^{\frac{1}{k}}$ of a star graph, for every positive integers $r$, $m$, $k$ and $n$. Particularly, it is obtained that $2\le {\chi }_r(P_m\times S_n^{\frac{1}{k}})\le 2n+1$.

In this paper, the $b$-coloring problem is solved for every subdivision-edge neighborhood corona of paths, cycles, stars and complete graphs. In addition, some exact values and sharp bounds are established for the $b$-chromatic number of subdivision-edge neighborhood coronas of these graphs with any other graph.

Let $\mathcal{𝒢}$ be a simple connected graph consisting of n vertices and m edges. In a proper $l$-coloring, an $r$-dynamic coloring of a graph $\mathcal{𝒢}$ is one in which each vertex’s neighbors are provided at least min $\{r,d(k)\}$ different colors. The $r$-dynamic chromatic number of graph $\mathcal{𝒢}$, given as ${\chi }_r(\mathcal{𝒢})$, is the minimal $l$ such that the graph has $r$-dynamic $l$ coloring of $\mathcal{𝒢}$. In this study, we combine a few common graphs to provide the $r$-dynamic coloring of the subdivision-edge neighborhood corona of path graph $P_{\mathrm{\text{s}}}$ and star graph $K_{1,\mathrm{\text{s}}}$. These graphs include path graph $P_{\mathrm{\text{q}}}$, cycle graph $C_{\mathrm{\text{q}}}$, complete graph $K_{\mathrm{\text{q}}}$, star graph $K_{1,\mathrm{\text{q}}}$, and double star graph $K_{1,\mathrm{\text{q}},\mathrm{\text{q}}}$.