Narrow Results

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 $𝔸(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.

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.

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 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.

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.

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.

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}.

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}}}$.