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.
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.
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.
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.
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 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.
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.