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.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
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.
Full text
Available for:
BFBNIB, FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SBCE, SBMB, UL, UM, UPUK
The study involved the analysis of the mares included in the brood stock between 1989-2018 and the public breeding stallions registered in the ranking sheets ranged from 2000-2010 of the Shagya ...Arabian horse breed, from the Radauti Stud farm, Suceava county, Romania. The dynamics of the average values of height, heart girth, and cannon girth were studied for both breeders category, to follow the evolution of the breed within the stud. The average values of the female’s height ranged from 156.7±0.069 cm to 159.9±0.102 cm; the average values for heart girth felt within the 180.1±0.151 cm - 180.8±0.153 cm interval; the average values of cannon girth varied between the 18.0±0.11 cm to 18.8±0.09 cm. The minimal value for height at withers in stallions was 157.66±1.21 cm while the maximal was 161.22±0.84 cm; average values of the hearth girth varied between 177.25±4.09 cm and 183.33±1.83 cm; cannon girth had average values of 18.5±0.77 - 19.16±0.31 cm. On the morphometric indices, it was found that stallions had higher values of massiveness index (113.21%) vs. mares (113.06%) and for the dactylo-thoracic index, as well (stallions had 11.11% and the mares 10.55%), while the bone index was higher in females (11.93%) vs. males (11.81%).
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 augmented Zagreb index (AZI) of a graph G is the sum of the weights d(u)d(v)/(d(u)+d(v)−2)3 over all edges uv of G, where d(u) is the degree of the vertex u in G. Let Ung be the set of all ...unicyclic graphs on n vertices with girth g. In this paper, we prove that if G is a graph with the maximum AZI in Ung, such that n≥32(g−2)+451 and g≥4, then G is a sunlet graph, i.e. G is a unicyclic graph such that removing all leaves gives a cycle. Furthermore, we have proven that G is always a good sunlet graph, in which all leaves are adjacent to the vertices in the cycle in a regular pattern. Finally we propose a new tool that could help to characterize the graph with the maximum AZI in Ung.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Conca and Varbaro (2020) 7 showed the equality of depth of a graded ideal and its initial ideal in a polynomial ring when the initial ideal is square-free. In this paper, we give some beautiful ...applications of this fact in the study of Cohen-Macaulay binomial edge ideals. We prove that for the characterization of Cohen-Macaulay binomial edge ideals, it is enough to consider only “biconnected graphs with some whisker attached” and this is done by investigating the initial ideals. We give several necessary conditions for a binomial edge ideal to be Cohen-Macaulay in terms of smaller graphs. Also, under a hypothesis, we give a sufficient condition for Cohen-Macaulayness of binomial edge ideals in terms of blocks of graphs. Moreover, we show that a graph with Cohen-Macaulay binomial edge ideal has girth less than 5 or equal to infinity.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
A vertex coloring of a graph $G$ is called injective if any two vertices with a common neighbor receive distinct colors. A graph $G$ is injectively $k$-choosable if any list $L$ of admissible colors ...on $V(G)$ of size $k$ allows an injective coloring $\varphi$ such that $\varphi(v)\in L(v)$ whenever $v\in V(G)$. The least $k$ for which $G$ is injectively $k$-choosable is denoted by $\chi_{i}^{l}(G)$. For a planar graph $G$, Bu et al.~proved that $\chi_{i}^{l}(G)\leq\Delta+6$ if girth $g\geq5$ and maximum degree $\Delta(G)\geq8$. In this paper, we improve this result by showing that $\chi_{i}^{l}(G)\leq\Delta+6$ for $g\geq5$ and arbitrary $\Delta(G)$. KCI Citation Count: 0
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.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
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.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
PDF
