Narrow Results

In this paper we deal with the layout of Trivalent Cayley Interconnection Networks. Namely, we prove that a lower bound on their layout area is Ω(2^n-1× 2^n-1) and we exhibit some methods to lay these networks out in O(2^n-1× 2^n-1).

We piont out that these layout methods work for other networks decomposable into equal length cycles connected by following fixed rules.

In this paper, we consider the concept of the average edge-connectivity $\overline{{\kappa }^{\prime }}(G)$ of a graph $G$, defined to be the average, over all pairs of vertices, of the maximum number of edge-disjoint paths connecting these vertices. Kim and O previously proved that $\overline{{\kappa }^{\prime }}(G)\left(\genfrac{}{}{0ex}{}{n}{2}\right)\ge \left(\genfrac{}{}{0ex}{}{n}{2}\right)+\frac{7n+58}{4}$ for any connected cubic graph on $n\ge 6$ vertices. We refine their result by showing that

A graph structure is a useful tool in solving the combinatorial problems in different areas of computer science and computational intelligence systems. In this paper, we introduce the concept of cubic soft graph, complete cubic soft graph, (internal, external) cubic soft graphs and investigate some of their properties. Then we deal with fundamental operations, union, intersection, Cartesian product, composition of cubic soft graphs and illustrate these notions by several examples. We prove that cubic soft graphs under these operations are also a cubic soft graph. Finally, we describe an application of cubic soft graphs in decision making.

A set S of vertices of a graph G is an outer-connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraph induced by V\S is connected. The outer-connected domination number is the minimum size of such a set. We present an infinite family of 2-connected cubic graphs, in which the number of vertices in a longest path are much less than the half of their orders. This disprove a recent conjecture posed by Akhbari, Hasni, Favaron, Karami, Sheikholeslami.

A $(v,b,g(G),r,{\lambda }_i)$-design over regular graph $G=(V,E)$ of degree $k$ is an ordered pair $D=(V,B)$, where $\left|V\right|=v$ and $B$ is the set of geodetic sets in $G$ called blocks such that two vertices $\alpha$ and $\beta$ which are $i^{\mathrm{\text{th}}}$ associates occur together in ${\lambda }_i$ blocks, the numbers ${\lambda }_i$ being independent of the choice of the pair $\alpha$ and $\beta$. In this paper, we obtain Partially Balanced Incomplete Block (PBIB)-designs arising from geodetic sets in some classes of graphs. Also, we give a complete list of PBIB-designs with respect to the geodetic sets for cubic graphs of order at most $12$. The discussion of non-existence of some designs corresponding to geodetic sets from certain graphs concludes the paper.

A locating-dominating set is a subset of vertices representing “detectors” in a graph G which can locate an “intruder” given that each detector covers its closed neighborhood and can distinguish its own location from its neighbors. We explore a fault-tolerant variant of locating-dominating sets, called error-detecting locating-dominating (DET:LD) sets, which can tolerate one false negative. The concept of DET:LD sets was originally introduced in 2002, along with several properties in various classes of graphs; we extend this work by fully characterizing DET:LD sets for general graphs and establishing existence criteria. We prove that the problem of determining the minimum density of a DET:LD set in arbitrary graphs is NP-complete. Additionally, we determine that the minimum density in cubic graphs is at least $\frac{3}{5}$, and we show an infinite family of cubic graphs achieving this density.