Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStrong Menger connectedness of augmented $k$-ary $n$-cubes
76
0
0.0
(
0
)
Added by
Mei-Mei Gu
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A connected graph $G$ is called strongly Menger (edge) connected if for any two distinct vertices $x,y$ of $G$, there are $min {{rm deg}_G(x), {rm deg}_G(y)}$ vertex(edge)-disjoint paths between $x$ and $y$. In this paper, we consider strong Menger (edge) connectedness of the augmented $k$-ary $n$-cube $AQ_{n,k}$, which is a variant of $k$-ary $n$-cube $Q_n^k$. By exploring the topological proprieties of $AQ_{n,k}$, we show that $AQ_{n,3}$ for $ngeq 4$ (resp. $AQ_{n,k}$ for $ngeq 2$ and $kgeq 4$) is still strongly Menger connected even when there are $4n-9$ (resp. $4n-8$) faulty vertices and $AQ_{n,k}$ is still strongly Menger edge connected even when there are $4n-4$ faulty edges for $ngeq 2$ and $kgeq 3$. Moreover, under the restricted condition that each vertex has at least two fault-free edges, we show that $AQ_{n,k}$ is still strongly Menger edge connected even when there are $8n-10$ faulty edges for $ngeq 2$ and $kgeq 3$. These results are all optimal in the sense of the maximum number of tolerated vertex (resp. edge) faults.
rate research
Read More
Let $P$ be a set of $n$ points in general position in the plane. A subset $I$ of $P$ is called an emph{island} if there exists a convex set $C$ such that $I = P cap C$. In this paper we define the emph{generalized island Johnson graph} of $P$ as the graph whose vertex consists of all islands of $P$ of cardinality $k$, two of which are adjacent if their intersection consists of exactly $l$ elements. We show that for large enough values of $n$, this graph is connected, and give upper and lower bounds on its diameter.
In this paper we study random induced subgraphs of the binary $n$-cube, $Q_2^n$. This random graph is obtained by selecting each $Q_2^n$-vertex with independent probability $lambda_n$. Using a novel construction of subcomponents we study the largest component for $lambda_n=frac{1+chi_n}{n}$, where $epsilonge chi_nge n^{-{1/3}+ delta}$, $delta>0$. We prove that there exists a.s. a unique largest component $C_n^{(1)}$. We furthermore show that $chi_n=epsilon$, $| C_n^{(1)}|sim alpha(epsilon) frac{1+chi_n}{n} 2^n$ and for $o(1)=chi_nge n^{-{1/3}+delta}$, $| C_n^{(1)}| sim 2 chi_n frac{1+chi_n}{n} 2^n$ holds. This improves the result of cite{Bollobas:91} where constant $chi_n=chi$ is considered. In particular, in case of $lambda_n=frac{1+epsilon} {n}$, our analysis implies that a.s. a unique giant component exists.
A $k$-matching $M$ of a graph $G=(V,E)$ is a subset $Msubseteq E$ such that each connected component in the subgraph $F = (V,M)$ of $G$ is either a single-vertex graph or $k$-regular, i.e., each vertex has degree $k$. In this contribution, we are interested in $k$-matchings within the four standard graph products: the Cartesian, strong, direct and lexicographic product. As we shall see, the problem of finding non-empty $k$-matchings ($kgeq 3$) in graph products is NP-complete. Due to the general intractability of this problem, we focus on distinct polynomial-time constructions of $k$-matchings in a graph product $Gstar H$ that are based on $k_G$-matchings $M_G$ and $k_H$-matchings $M_H$ of its factors $G$ and $H$, respectively. In particular, we are interested in properties of the factors that have to be satisfied such that these constructions yield a maximum $k$-matching in the respective products. Such constructions are also called well-behaved and we provide several characterizations for this type of $k$-matchings. Our specific constructions of $k$-matchings in graph products satisfy the property of being weak-homomorphism preserving, i.e., constructed matched edges in the product are never projected to unmatched edges in the factors. This leads to the concept of weak-homomorphism preserving $k$-matchings. Although the specific $k$-matchings constructed here are not always maximum $k$-matchings of the products, they have always maximum size among all weak-homomorphism preserving $k$-matchings. Not all weak-homomorphism preserving $k$-matchings, however, can be constructed in our manner. We will, therefore, determine the size of maximum-sized elements among all weak-homomorphims preserving $k$-matching within the respective graph products, provided that the matchings in the factors satisfy some general assumptions.
A strong edge colouring of a graph is an assignment of colours to the edges of the graph such that for every colour, the set of edges that are given that colour form an induced matching in the graph. The strong chromatic index of a graph $G$, denoted by $chi_s(G)$, is the minimum number of colours needed in any strong edge colouring of $G$. A graph is said to be emph{chordless} if there is no cycle in the graph that has a chord. Faudree, Gyarfas, Schelp and Tuza~[The Strong Chromatic Index of Graphs, Ars Combin., 29B (1990), pp.~205--211] considered a particular subclass of chordless graphs, namely the class of graphs in which all the cycle lengths are multiples of four, and asked whether the strong chromatic index of these graphs can be bounded by a linear function of the maximum degree. Chang and Narayanan~[Strong Chromatic Index of 2-degenerate Graphs, J. Graph Theory, 73(2) (2013), pp.~119--126] answered this question in the affirmative by proving that if $G$ is a chordless graph with maximum degree $Delta$, then $chi_s(G) leq 8Delta -6$. We improve this result by showing that for every chordless graph $G$ with maximum degree $Delta$, $chi_s(G)leq 3Delta$. This bound is tight up to to an additive constant.
Random directed graphs $D(n,p)$ undergo a phase transition around the point $p = 1/n$, and the width of the transition window has been known since the works of Luczak and Seierstad. They have established that as $n to infty$ when $p = (1 + mu n^{-1/3})/n$, the asymptotic probability that the strongly connected components of a random directed graph are only cycles and single vertices decreases from 1 to 0 as $mu$ goes from $-infty$ to $infty$. By using techniques from analytic combinatorics, we establish the exact limiting value of this probability as a function of $mu$ and provide more properties of the structure of a random digraph around, below and above its transition point. We obtain the limiting probability that a random digraph is acyclic and the probability that it has one strongly connected complex component with a given difference between the number of edges and vertices (called excess). Our result can be extended to the case of several complex components with given excesses as well in the whole range of sparse digraphs. Our study is based on a general symbolic method which can deal with a great variety of possible digraph families, and a version of the saddle-point method which can be systematically applied to the complex contour integrals appearing from the symbolic method. While the technically easiest model is the model of random multidigraphs, in which multiple edges are allowed, and where edge multiplicities are sampled independently according to a Poisson distribution with a fixed parameter $p$, we also show how to systematically approach the family of simple digraphs, where multiple edges are forbidden, and where 2-cycles are either allowed or not. Our theoretical predictions are supported by numerical simulations, and we provide tables of numerical values for the integrals of Airy functions that appear in this study.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
