In this paper, we consider the lengths of cycles that can be embedded on the edges of the generalized pancake graphs which are the Cayley graph of the generalized symmetric group S(m,n), generated by ...prefix reversals. The generalized symmetric group S(m,n) is the wreath product of the cyclic group of order m and the symmetric group of order n!. Our main focus is the underlying undirected graphs, denoted by Pm(n). In the cases when the cyclic group has one or two elements, these graphs are isomorphic to the pancake graphs and burnt pancake graphs, respectively. We prove that when the cyclic group has three elements, P3(n) has cycles of all possible lengths, thus resembling a similar property of pancake graphs and burnt pancake graphs. Moreover, P4(n) has all the even-length cycles. We utilize these results as base cases and show that if m>2 is even, Pm(n) has all cycles of even length starting from its girth to a Hamiltonian cycle. Moreover, when m>2 is odd, Pm(n) has cycles of all lengths starting from its girth to a Hamiltonian cycle. We furthermore show that the girth of Pm(n) is min{m,6} if m≥3, thus complementing the known results for m=1,2.
Efficient Search of Girth-Optimal QC-LDPC Codes Tasdighi, Alireza; Banihashemi, Amir H.; Sadeghi, Mohammad-Reza
IEEE transactions on information theory,
2016-April, 2016-4-00, 20160401, Volume:
62, Issue:
4
Journal Article
Peer reviewed
In this paper, we study the cycle structure of quasi-cyclic (QC) low-density parity-check (LDPC) codes with the goal of obtaining the shortest code with a given degree distribution and girth. We ...focus on QC-LDPC codes, whose Tanner graphs are cyclic liftings of fully connected base graphs of size 3 × n, n ≥ 4, and obtain minimal lifting degrees that result in girths 6 and 8. This is performed through an efficient exhaustive search, and as a result, we also find all the possible non-isomorphic codes with the same minimum block length, girth, and degree distribution. The exhaustive search, which is ordinarily a formidable task, is made possible by pruning the search space of many codes that are isomorphic to those previously examined in the search process. Many of the pruning techniques proposed in this paper are also applicable to QC-LDPC codes with base graphs other than the 3 × n fully connected ones discussed here, as well as to codes with a larger girth. To further demonstrate the effectiveness of the pruning techniques, we use them to search for QC-LDPC codes with girths 10 and 12, and find a number of such codes that have a shorter block length compared with the best known similar codes in the literature. In addition, motivated by the exhaustive search results, we tighten the lower bound on the block length of QC-LDPC codes of girth 6 constructed from fully connected 3 × n base graphs, and construct codes that achieve the lower bound for an arbitrary value of n ≥ 4.
Let
Γ denote a finite, connected, simple graph. For an edge
e of
Γ let
n
(
e
) denote the number of girth cycles containing
e. For a vertex
v of
Γ let
{
e
1
,
e
2
,
…
,
e
k
} be the set of edges ...incident to
v ordered such that
n
(
e
1
)
≤
n
(
e
2
)
≤
⋯
≤
n
(
e
k
). Then
(
n
(
e
1
)
,
n
(
e
2
)
,
…
,
n
(
e
k
)
) is called the signature of
v. The graph
Γ is said to be girth‐regular if all of its vertices have the same signature. Let
Γ be a girth‐regular graph with girth
g
=
2
d and signature
(
a
1
,
a
2
,
…
,
a
k
). It is known that in this case we have
a
k
≤
(
k
−
1
)
d. In this paper we show that if
a
k
=
(
k
−
1
)
d
−
ϵ for some nonnegative integer
ϵ
<
k
−
1, then
ϵ
=
0. We also show that the above bound on
ϵ is sharp by displaying examples of girth‐regular graphs with
a
k
=
(
k
−
1
)
d
−
(
k
−
1
) for some values of
k and
d (in particular, for
d
=
2), and construct geometric examples where
a
k is not far from
(
k
−
1
)
d.
Let G be an undirected simple connected graph. We say a vertex u is eccentric to a vertex v in G if d(u,v)=max{d(v,w):w∈V(G)}. The eccentric graph of G, say Ec(G), is a graph defined on the same ...vertex set as of G and two vertices are adjacent if one is eccentric to the other. We find the structure and the girth of the eccentric graph of trees and see that the girth of the eccentric graph of a tree can either be zero, three, or four. Further, we study the structure of the eccentric graph of the Cartesian product of graphs and prove that the girth of the eccentric graph of the Cartesian product of trees can only be zero, three, four or six. Furthermore, we provide a comprehensive classification when the eccentric girth assumes these values. We also give the structure of the eccentric graph of the grid graphs and the Cartesian product of two cycles. Finally, we determine the conditions under which the eccentricity matrix of the Cartesian product of trees becomes invertible.
Spatially coupled low-density parity-check convolutional codes (SC-LDPC-CCs) are a class of capacity approaching LDPC codes with low message recovery latency when a sliding window decoding is used. ...Recently, an edge spreading (unwrapping) approach has been proposed to generate a class of array-based SC-LDPC-CCs by partitioning a spreading matrix into a number of components. Applying the spreading matrix E as the exponent matrix of a QC-LDPC code, the relationship of 4-cycles between E and the corresponding SC-LDPC-CCs is investigated in two cases, in this paper. Then, by defining a new class of integer finite sequences, called good sequences , a class of 4-cycle free SC-LDPC-CCs is constructed by an explicit simple method that can achieve (in most cases) the minimum coupling widths. The constructed codes enjoy a relative advantage in flexibility in rate and lengths, simple constructions, and minimal short-cycle distributions, which can show themselves in improving the bit-error-rate performances.
The cultivation of elite latex-timber clones that exhibit both enhanced NR and wood production has become a key objective in current Hevea brasiliensis breeding programs. The girth and dry rubber ...yield (DRY) are two crucial indicators for evaluating the latex-timber characteristics of Hevea trees. However, the quantitative trait locus (QTL) and candidate genes identified for these traits are still limited. Here, a genome-wide association study (GWAS) was performed in a Whickham germplasm offspring to identify genetic variants associated with girth and DRY. Girth and DRY phenotypes were measured for three consecutive years. Meanwhile, a total of 7835,736 high-confidence SNPs were identified from 218 Hevea accessions. Remarkably, the population exhibited a high level of genetic diversity, coupled with a rapid decline in linkage disequilibrium, and was roughly grouped into three subgroups by population structure analysis. A total of 17 and 76 SNPs, respectively, correlated significantly with girth DRY, and corresponded to 31 and 284candidate genes for girth and DRY. To further assess the candidates, gene expression analyses were performed separately on four types of Hevea tree tissues and two distinct groups exhibiting notable girth or DRY phenotypic differences. Eventually, a cullin protein and an iridoid oxidase protein were identified as prospective girth regulators, whereas two chloroplast thylakoid membrane proteins and an auxin-repressed protein were implicated in shaping the performance of DRY. These findings contribute to a deeper understanding of the genetic foundations of girth and DRY, as well as molecular-assisted breeding of latex-timber rubber clones.
Display omitted
•Genome-wide association study on 218 offspring accessions of Hevea Wickham germplasm to identify girth and rubber yield QTLs.•Substantial genetic diversity observed in this progeny population.•17 and 76 significant SNPs associated with girth and rubber yield, respectively.•The cullin and iridoid oxidase identified as promising candidates for regulating girth development.•The chloroplast thylakoid membrane and auxin-repressed proteins identified as candidates affecting rubber yield.
Three girth weld cracking events were found by X-ray inspection in one natural gas station. To determine the failure cause, one of the three failure events was studied by visual inspection, ...nondestructive testing, microstructure examination, scanning electronic microscopy (SEM) coupled with energy dispersive spectrometry (EDS), blasting tests, finite element simulations and a series physical and chemical tests. The results revealed that the welding defects were original failure factor, and these welding defects led to crack initiation and propagation through the wall thickness under three aspects of stress concentration effects with internal pressure. The stress concentration effects were originated from the unqualified inner chamfering angle, unequal wall thickness, and inherent shape of tee pipe. The reason causing welding defects of girth weld is that the slag inclusions were not cleaned up timely, and then the slag inclusions led to the existence of welding defects.
Display omitted
•The failure causes of girth weld cracking of tee pipe were determined.•The stress concentration effect was analyzed to determine failure cause.•The blasting tests was carried out to analyze the effect of welding process.•The influencing mechanism of welding defect on girth weld cracking was clarified.
An edge-girth-regular graph egr(v,k,g,λ), is a k-regular graph of order v, girth g and with the property that each of its edges is contained in exactly λ distinct g-cycles. An egr(v,k,g,λ) is called ...extremal for the triple (k,g,λ) if v is the smallest order of any egr(v,k,g,λ). In this paper, we introduce two families of edge-girth-regular graphs. The first one is a family of extremal egr(2q2,q,6,(q−1)2(q−2)) for any prime power q≥3. The second one is a family of egr(q(q2+1),q,5,λ) for λ≥q−1 and q≥8 an odd power of 2. In particular, if q=8 we have that λ=q−1. Finally, we construct two egr(32,5,5,12) and we prove that they are extremal.
The adaptable choosability of a multigraph G $G$, denoted cha(G) ${\text{ch}}_{a}(G)$, is the smallest integer k $k$ such that any edge labelling, τ $\tau $, of G $G$ and any assignment of lists of ...size k $k$ to the vertices of G $G$ permits a list colouring, σ $\sigma $, of G $G$ such that there is no edge e=uv $e=uv$ where τ(e)=σ(u)=σ(v) $\tau (e)=\sigma (u)=\sigma (v)$. Here we show that for a multigraph G $G$ with maximum degree Δ ${\rm{\Delta }}$ and no cycles of length 3 or 4, cha(G)≤(22+o(1))Δ∕ln Δ ${\text{ch}}_{a}(G)\,\le (2\sqrt{2}+o(1))\sqrt{{\rm{\Delta }}\unicode{x02215}\mathrm{ln}\unicode{x0200A}{\rm{\Delta }}}$. Under natural restrictions we can show that the same bound holds for the conflict choosability of G $G$, which is a closely related parameter recently defined by Dvořák, Esperet, Kang and Ozeki.
PDF
