In this paper, we propose new constructions for regular girth-8 quasi-cyclic low-density parity-check (QC-LDPC) codes based on circulant permutation matrices (CPM). The constructions assume ...symmetries in the structure of the parity-check matrix and employ a greedy exhaustive search algorithm to find the permutation shifts of the CPMs. As a result of symmetries, the new codes have a more compact representation compared with their counterparts. In majority of cases, also, they achieve the girth 8 at a shorter block length for the same degree distribution (code rate). Deterministic (explicit) constructions are also presented to expand the proposed parity-check matrices to larger block lengths and higher rates. The proposed long high-rate codes are often substantially shorter than regular girth-8 QC-LDPC codes of similar rate in the literature. Simulation results demonstrate that the proposed symmetric codes have competitive performance in comparison with similar existing QC-LDPC codes that lack symmetry.
We prove upper bounds for the spectral radius ρ(G) of an n-vertex graph with given maximum degree and girth at least 2ℓ+1. This extends the previous result of 9 regarding graphs with girth at least ...five. When ℓ=3 or |V(G)| is relatively small compared with the maximum degree, our upper bounds are sharp. In addition, for a tree T, we provide an upper bound for the spectral radius of an n-vertex T-free graph with given maximum degree. This bound is also sharp for a certain class of trees.
Asymptotics in percolation on high‐girth expanders Krivelevich, Michael; Lubetzky, Eyal; Sudakov, Benny
Random structures & algorithms,
July 2020, 2020-07-00, 20200701, Volume:
56, Issue:
4
Journal Article
Peer reviewed
Open access
We consider supercritical bond percolation on a family of high‐girth d‐regular expanders. The previous study of Alon, Benjamini and Stacey established that its critical probability for the appearance ...of a linear‐sized (“giant”) component is pc=1/(d−1). Our main result recovers the sharp asymptotics of the size and degree distribution of the vertices in the giant and its 2‐core at any p>pc. It was further shown in the previous study that the second largest component, at any 0<p<1, has size at most nω for some ω<1. We show that, unlike the situation in the classical Erdős‐Rényi random graph, the second largest component in bond percolation on a regular expander, even with an arbitrarily large girth, can have size nω′ for ω′ arbitrarily close to 1. Moreover, as a by‐product of that construction, we answer negatively a question of Benjamini on the relation between the diameter of a component in percolation on expanders and the existence of a giant component. Finally, we establish other typical features of the giant component, for example, the existence of a linear path.
Introduction: Blood Flow Restriction Training (BFRT) was developed by Southeast Asia Treaty Organisation (SATO) in Japan in 1966. BFRT is a method that mimics the effects of high-intensity training ...by combining low-intensity exercise with blood flow obstruction. It involves limb compression using compression cuffs to limit venous outflow and minimise arterial inflow during rehabilitation training. By allowing individuals to lift smaller loads and increase strength training gains, BFRT can reduce the overall stress exerted on the limb. Aim: To assess the difference in muscle girth and blood pressure after a single bout of BFRT. Materials and Methods: This was a single-blinded, singlesite pretest, post-test quasi-experimental study. A total of 30 subjects were enrolled (16 females and 14 males) between the ages of 18 to 25 years. This study was conducted at the Department of Physiotherapy, Galgotias University, Greater Noida, Uttar Pradesh, India. Outcome measures included muscle girth measured using a flexible tape and blood pressure using an automatic oscillometric device (Omron Hem 7113, São Paulo, Brazil). Paired t-test and Wilcoxon test were performed using Statistical Package for Social Sciences (SPSS) software version 20.0. Results: It was found that an acute bout of BFRT caused improvement in all outcome measures. There was a statistically significant increase in muscle girth and blood pressure after BFRT (p-value<0.001). Conclusion: There was a significant increase in blood pressure (both Systolic Blood Pressure (SBP) and Diastolic Blood Pressure (DBP)) and muscle girth after BFRT with no reported adverse effects.
Unicyclic graph is one kind of typical graph for indices basing degree of vertex. Various chemical structures can be exhibited in unicyclic graph as well. A graph is said to be unicyclic if the graph ...is connected and |V(G)|=|E(G)|. Recently, the Sombor index, which is defined bySO=SO(G)=∑uv∈E(G)dG2(u)+dG2(v), was proposed by Gutman. This paper establishes distinct bounds for this index of unicyclic graph with girth l, as well as specific bounds of chemical unicyclic graph with girth l.
•Some bounds and extremal graphs of Sombor index over unicyclic graph are given.•The minimum value and graph of Sombor index over chemical unicyclic graph are gotten.•With a order condition, the maximum value and graphs of Sombor index over chemical unicyclic graph are determined.
Generalized Turán problems for even cycles Gerbner, Dániel; Győri, Ervin; Methuku, Abhishek ...
Journal of combinatorial theory. Series B,
November 2020, 2020-11-00, Volume:
145
Journal Article
Peer reviewed
Open access
Given a graph H and a set of graphs F, let ex(n,H,F) denote the maximum possible number of copies of H in an F-free graph on n vertices. We investigate the function ex(n,H,F), when H and members of F ...are cycles. Let Ck denote the cycle of length k and let Ck={C3,C4,…,Ck}. We highlight the main results below.(i)We show that ex(n,C2l,C2k)=Θ(nl) for any l,k≥2. Moreover, in some cases we determine it asymptotically: We show that ex(n,C4,C2k)=(1+o(1))(k−1)(k−2)4n2 and that the maximum possible number of C6's in a C8-free bipartite graph is n3+O(n5/2).(ii)Erdős's Girth Conjecture states that for any positive integer k, there exist a constant c>0 depending only on k, and a family of graphs {Gn} such that |V(Gn)|=n, |E(Gn)|≥cn1+1/k with girth more than 2k.Solymosi and Wong 37 proved that if this conjecture holds, then for any l≥3 we have ex(n,C2l,C2l−1)=Θ(n2l/(l−1)). We prove that their result is sharp in the sense that forbidding any other even cycle decreases the number of C2l's significantly: For any k>l, we have ex(n,C2l,C2l−1∪{C2k})=Θ(n2). More generally, we show that for any k>l and m≥2 such that 2k≠ml, we have ex(n,Cml,C2l−1∪{C2k})=Θ(nm).(iii)We prove ex(n,C2l+1,C2l)=Θ(n2+1/l), provided a stronger version of Erdős's Girth Conjecture holds (which is known to be true when l=2,3,5). This result is also sharp in the sense that forbidding one more cycle decreases the number of C2l+1's significantly: More precisely, we have ex(n,C2l+1,C2l∪{C2k})=O(n2−1l+1), and ex(n,C2l+1,C2l∪{C2k+1})=O(n2) for l>k≥2.(iv)We also study the maximum number of paths of given length in a Ck-free graph, and prove asymptotically sharp bounds in some cases.
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.
In 1994, Thomassen famously proved that every planar graph is 5-choosable,
resolving a conjecture initially posed by Vizing and, independently, Erd˝os, Rubin, and Taylor in the 1970s. Later, ...Thomassen proved that every planar graph of girth at least five is 3-choosable. In this paper, we introduce the concept of a local girth list assignment: a list assignment wherein the list size of a vertex depends not on the girth of the graph, but rather on the length of the shortest cycle in which the vertex is contained. We give a local list colouring theorem unifying the two theorems of Thomassen mentioned above. In particular, we show that if G is a planar graph and L is a list assignment for G such that |L(v)| ≥ 3 for all v ∈ V(G); |L(v)| ≥ 4 for every vertex v contained in a 4-cycle; and |L(v)| ≥ 5 for every v contained in a triangle, then G admits an L-colouring.
In this paper, we study the relationships between the girth of the Tanner graph of a quasi-cyclic (QC) protograph low-density parity-check (LDPC) code, the lifting degree, and the size and the ...structure of the base graph. As a result, for a given base graph, we derive a lower bound on the lifting degree as a necessary condition for the lifted graph to have a certain girth. This also provides an upper bound on the girth of the family of graphs lifted from a given base graph with a given lifting degree. The upper bounds derived here, which are applicable to both regular and irregular base graphs with no parallel edges, are in some cases more general and in some other cases tighter than the existing bounds. The results presented in this work can be used to design cyclic liftings with relatively small degree and relatively large girth. As an example, we present new QC protograph LDPC code constructions with girth 8 using fully connected base graphs. These constructions provide upper bounds on the lifting degree required for achieving girth 8 using fully connected base graphs.
PDF
