Search

A bisection of a graph is a bipartition of its vertex set in which the two parts differ in size by at most 1, and its size is the number of edges which across the two parts. Let G be a graph with n vertices, m edges and degree sequence d 1 , d 2 , ... , d n . Motivated by a few classical results on Max-Cut of graphs, Lin and Zeng proved that if G is { C 4 , C 6 } -free and has a perfect matching, then G has a bisection of size at least m / 2 + Ω (∑ i = 1 n d i ) , and conjectured the same bound holds for C 4 -free graphs with perfect matchings. In this paper, we confirm the conjecture under the additional condition that G is C 5 -free. [ABSTRACT FROM AUTHOR]

Let B n denote the family of all maximal bipartite planar graphs on n vertices. Given a family of graphs H , let B n (H) denote the family of all maximal bipartite planar graphs on n vertices which are not H -free. For graph G and a family of graphs H , if G is not H -free, the rainbow number of H in G , denoted by r b (G , H) , is the minimum positive integer t , such that any t -edge-colored graph G contains a rainbow copy of some graph in H. The rainbow number of H in maximal bipartite planar graph, denoted by r b (B n (H) , H) , is defined as max { r b (G , H) | G ∈ B n (H) }. A cycle on l vertices is denoted by C l. The graph obtained by arbitrarily adding one pendant edge at one vertex of a cycle C l is denoted by C l +. For any positive integer k , let C k ≔ { C 4 , C 6 , ... , C 2 k + 2 } and C k , 2 i 0 + ≔ (C k ∖ { C 2 i 0 }) ∪ { C 2 i 0 + } for some i 0 ∈ { 2 , 3 , ... , k + 1 }. In this paper, we firstly prove that r b (B n , C k) = r b (B n , C k , 2 i 0 +) = n + n − 2 k + 2 − 1 for any n ≥ max { 2 k + 2 , 5 } and k + 1 ≥ i 0 ≥ 2. We then obtain that r b (B n (H) , H) = 2 n − 4 for any n ≥ | V (H) | and k ≥ 3 , where H ∈ { C 2 k , C 2 k + }. [ABSTRACT FROM AUTHOR]

Consider a connected simple graph G. Given a spanning tree T of G , for each edge e in G but not in T , a cycle C e is formed by adding the edge e to the path in T that connects the endpoints of e. The Minimum Spanning Tree Cycle Intersection problem (MSTCI for short) consists in finding a spanning tree for G that minimizes the number of intersections between this type of cycles. This problem was introduced in 2021 and its solution turned out to be difficult for general graphs, without an efficient algorithm to solve it. It was then conjectured that a solution of the problem for a graph that has a universal vertex u is the star centered at u. The conjecture was quickly proven true. In this note, we give a proof of the conjecture that is shorter than the one that has already been published. It is based on a single lemma about domination. We also explore the connections between this lemma and some graph classes, like chordal graphs and dually chordal graphs. [ABSTRACT FROM AUTHOR]

Let A be the family of planar graphs without 4-cycles and 5-cycles. In 2013, Hill et al. proved that every graph G ∈ A has a partition dividing V (G) into three sets, where two of them are independent, and the other induces a graph with a maximum degree at most 3. In 2021 Cho, Choi, and Park conjectured that every graph G ∈ A has a partition dividing V (G) into two sets, where one set induces a forest, and the other induces a forest with a maximum degree at most 2. In this paper, we show that every graph G ∈ A has a partition dividing V (G) into two sets, where one set induces a forest, and the other induces a disjoint union of paths and subdivisions of K 1 , 3. The result improves the aforementioned result by Hill et al. and yields progress toward the conjecture of Cho, Choi, and Park. [ABSTRACT FROM AUTHOR]

• The elastocaloric effect of natural rubber under different ambient temperature conditions was obtained. • Obtained the optimum ambient temperature for the elastocaloric effect of natural rubber elasticity. • Analytical temperature variation equations for cooling and heating natural convection were provided as a function of the Fourier (Fo) and Biot (Bi) numbers. Owing to its high efficiency and specific refrigeration power, elastocaloric refrigeration is a promising technology that is potentially endowed with replacing the conventional steam compression refrigeration. Here, experimental results on the elastocaloric cooling process of natural rubber are presented, achieving a maximum temperature drop during unloading of the natural rubber of 41.30 K with a temperature difference of 68 K between hot and cold ends at an ambient temperature of 253.13 K. Moreover, analytical equations are provided for the temperature variation of cooling and heating natural convection as a function of Fo and Bi numbers, which are fitted to the experimental data and can be used to provide predictions for future elastocaloric refrigeration equipment. Thus, the study unravels the potential of natural rubber as a promising elastocaloric material and its key properties for refrigeration technology. [ABSTRACT FROM AUTHOR]

The Cartesian product of two simple graphs G and H is the graph G □ H whose vertex set is V (G) × V (H) and whose edge set is the set of all pairs (u 1 , v 1) (u 2 , v 2) such that either u 1 u 2 ∈ E (G) and v 1 = v 2 , or v 1 v 2 ∈ E (H) and u 1 = u 2 . The fractional matching preclusion number of a graph G , denoted by f m p (G) , is the minimum number of edges whose deletion results in a graph with no fractional perfect matching. In this paper, we determine f m p (G □ H) when H is a cycle or a path of even order; Moreover, given any integers a , b with a ≥ 1 and 0 ≤ b ≤ a + 1 , we construct a graph G such that δ (G) = a and f m p (G □ H) = b when H is a path of odd order. [ABSTRACT FROM AUTHOR]

In 1975, P. Erdős proposed the problem of determining the maximum number f (n) of edges in a graph on n vertices in which any two cycles are of different lengths. Let f ∗ (n) be the maximum number of edges in a simple graph on n vertices in which any two cycles are of different lengths. Let M n be the set of simple graphs on n vertices and f ∗ (n) edges in which any two cycles are of different lengths. Let m c (n) be the maximum cycle length for all G ∈ M n . In this paper, it is proved that for n sufficiently large, m c (n) ≤ 15 16 n. We make the following conjecture: Conjecture. lim n → ∞ m c (n) n = 0. [ABSTRACT FROM AUTHOR]

We introduce the following cycle selection problem which is motivated by an application to kidney exchange problems. Given a directed graph G = (V , A) , a cycle selection is a subset of arcs B ⊆ A forming a union of directed cycles. A related optimization problem, the Maximum Weighted Cycle Selection problem can be defined as follows: given a weight w i , j ∈ R for all arcs (i , j) ∈ A , find a cycle selection B which maximizes w (B). We prove that this problem is strongly NP-hard. Next, we focus on cycle selections in complete directed graphs. We provide several ILP formulations of the problem: an arc formulation featuring an exponential number of constraints which can be separated in polynomial time, four extended compact formulations, and an extended non compact formulation. We investigate the relative strength of these formulations. We concentrate on the arc formulation and on the description of the associated cycle selection polytope. We prove that this polytope is full-dimensional, and that all the inequalities used in the arc formulation are facet-defining. Furthermore, we describe three new classes of facet-defining inequalities and a class of valid inequalities. We also consider the consequences of including additional constraints on the cardinality of a selection or on the length of the associated cycles. [ABSTRACT FROM AUTHOR]

We present a new Measure of Aggregate Trade Restrictions (MATR) using data from the IMF's Annual Report on Exchange Arrangements and Exchange Restrictions. MATR is strongly correlated with existing measures of trade restrictiveness but more comprehensive in terms of country and time coverage. Our measure is available for an unbalanced sample of up to 157 countries during 1949–2019. We use our new MATR to re-examine how trade restrictiveness varies with the business cycle. Our results confirm that trade restrictions are typically a-cyclical but there is an important difference across income groups: aggregate trade restrictions are a-cyclical in advanced economies but are counter-cyclical in EMDEs, especially in response to increases in unemployment. [ABSTRACT FROM AUTHOR]

We say that a sequence a 1... a 2t of integers is repetitive if a i = a i+t for every i ϵ {1,...,t}. A walk in a graph G is a sequence v 1... v r of vertices of G in which v i v i+1 ϵ E(G) for every i ϵ {1,..., r - 1}. Given a k -coloring c: V(G) → {1,..., k } of V(G) , we say that c is walk-nonrepetitive if for every t ϵ N, for every walk v 1... v 2t in G the sequence c(V 1)... c(v 2t) is not repetitive unless v i = v i+t for every i ϵ {1,..., t }, and the walk-nonrepetitive chromatic number σ (G) of G is the minimum k for which G has a walk-nonrepetitive k-coloring. Let C n denote the cycle with n vertices. In this paper we show that σ(C n) = 4 whenever n ≥ 4 and n ∉ {5,7}, which answers a question posed by Barát and Wood in 2008. [ABSTRACT FROM AUTHOR]

For bipartite graphs G 1 , G 2 , ... , G k , the bipartite Ramsey number b (G 1 , G 2 , ... , G k) is the least positive integer b , so that any coloring of the edges of K b , b with k colors, will result in a copy of G i in the i th color, for some i. For bipartite graphs G 1 and G 2 , the bipartite Ramsey number pair (a , b) , denoted by b p (G 1 , G 2) = (a , b) , is an ordered pair of integers such that for any blue-red coloring of the edges of K a ′ , b ′ , with a ′ ≥ b ′ , either a blue copy of G 1 exists or a red copy of G 2 exists if and only if a ′ ≥ a and b ′ ≥ b. In [4] , Faudree and Schelp considered bipartite Ramsey number pairs involving paths. Recently, Joubert, Hattingh and Henning showed, in [7] and [8] , that b p (C 2 s , C 2 s) = (2 s , 2 s − 1) and b (P 2 s , C 2 s) = 2 s − 1 , for sufficiently large positive integers s. In this paper we will focus our attention on finding exact values for bipartite Ramsey number pairs that involve cycles and odd paths. Specifically, let s and r be sufficiently large positive integers. We will prove that b p (C 2 s , P 2 r + 1) = (s + r , s + r − 1) if r ≥ s + 1 , b p (P 2 s + 1 , C 2 r) = (s + r , s + r) if r = s + 1 , and b p (P 2 s + 1 , C 2 r) = (s + r − 1 , s + r − 1) if r ≥ s + 2. [ABSTRACT FROM AUTHOR]

We study the hat guessing game on graphs. In this game, a player is placed on each vertex v of a graph G and assigned a colored hat from h (v) possible colors. Each player makes a deterministic guess on their hat color based on the colors assigned to the players on neighboring vertices, and the players win if at least one player correctly guesses his assigned color. If there exists a strategy that ensures at least one player guesses correctly for every possible assignment of colors, the game defined by 〈 G , h 〉 is called winning. The hat guessing number of G is the largest integer q so that if h (v) = q for all v ∈ G then 〈 G , h 〉 is winning. In this note, we determine whether 〈 G , h 〉 is winning for any h whenever G is a cycle, resolving a conjecture of Kokhas and Latyshev in the affirmative and extending it. We then use this result to determine the hat guessing number of every cactus graph, graphs in which every pair of cycles share at most one vertex. [ABSTRACT FROM AUTHOR]

Given a set F of graphs, we call a copy of a graph in F an F -graph. The F -isolation number of a graph G , denoted by ι (G , F) , is the size of a smallest subset D of the vertex set V (G) such that the closed neighbourhood of D intersects the vertex sets of the F -graphs contained by G (equivalently, G − N [ D ] contains no F -graph). Thus, ι (G , { K 1 }) is the domination number of G. The second author showed that if F is the set of cycles and G is a connected n -vertex graph that is not a triangle, then ι (G , F) ≤ ⌊ n 4 ⌋. This bound is attainable for every n and solved a problem of Caro and Hansberg. A question that arises immediately is how much smaller an upper bound can be if F = { C k } for some k ≥ 3 , where C k is a cycle of length k. The problem is to determine the smallest real number c k (if it exists) such that for some finite set E k of graphs, ι (G , { C k }) ≤ c k | V (G) | for every connected graph G that is not an E k -graph. The above-mentioned result yields c 3 = 1 4 and E 3 = { C 3 }. The second author also showed that if k ≥ 5 and c k exists, then c k ≥ 2 2 k + 1. We prove that c 4 = 1 5 and determine E 4 , which consists of three 4-vertex graphs and six 9-vertex graphs. The 9-vertex graphs in E 4 were fully determined by means of a computer program. A method that has the potential of yielding similar results is introduced. [ABSTRACT FROM AUTHOR]

The Erdős-Gyárfás conjecture asserts that every graph with minimum degree at least three has a cycle whose length is a power of 2. Let G be a graph with minimum degree at least 3. We show that if G contains no induced path of order 10, then G contains a cycle of length 4 or 8, and hence the conjecture holds in this case. [ABSTRACT FROM AUTHOR]

An edge colored graph is called rainbow if all the colors on its edges are distinct. A rainbow copy of a graph H in an edge colored graph G is a subgraph of G isomorphic to H such that the coloring restricted to H is rainbow. Let G and H be two graphs. The anti-Ramsey number A r (G , H) is the maximum number of colors in an edge coloring of G which has no rainbow copy of H. For n ≥ 3 , the n -prism is the cartesian product C n □ K 2 . In this paper, we determine the anti-Ramsey numbers for cycles in n -prisms. [ABSTRACT FROM AUTHOR]

Let G be a graph and T a spanning tree of G. For an edge e in G − T , there is a cycle in T ∪ { e }. We call those edges cycle-edges and those cycles tree-cycles. The intersection of two tree-cycles is the set of all edges in common. If the intersection of two distinct tree-cycles is not empty, we regard that as an intersection. The tree intersection number of T is the number of intersections among all tree-cycles of T. In this paper, we prove the conjecture, posed by Dubinsky et al. (2021), which states that if a graph admits a star spanning tree in which one vertex is adjacent to all other vertices, then the star spanning tree has the minimum tree intersection number. [ABSTRACT FROM AUTHOR]

• δ34S and concentrations of multiple S-phases measured in Permian-Triassic section. • First δ34S measurement of organic sulfur compounds in P-T section. • Opposing δ34S DBT and δ34S TRIS excursions reflect fluctuating ocean redox. • Dynamic diagenetic sulfurisation resolved by δ34S DBT , but not bulk kerogen. • Negative δ34S DBT-TRIS values identify organic sulfurisation with greater bias against 34S than pyritization. Sulfur cycle fluxes implicated in the Permian-Triassic mass extinction have traditionally been studied by the sulfur phase abundances in sedimentary rocks and the stable sulfur isotopic value (δ34S) of seawater sulfate inferred from mineral sulfate analyses. This information might be complemented by studies of the reduced inorganic sulfur and organic sulfur produced following bacterial sulfate reduction. To explore this potential the δ34S and concentration analyses of total reduced inorganic sulfur (TRIS) and organic sulfur – separately in the forms of kerogen (Ker) and individual organosulfur compounds, specifically dibenzothiophenes (DBTs) – has been conducted on sediments across the Late Permian to Early Triassic marine type section of Meishan-1 (South China). The relatively steady δ34S profiles (e.g., < 5 ‰ variation) of all sulfur phases measured through much of the late Permian were indicative of a primary seawater sulfate control, but other biogeochemical modulators caused prominent δ34S fluctuations of TRIS and DBT adjacent to the extinction event. The late Triassic δ34S TRIS profile of Meishan-1 displayed a notable 34S enrichment (+15 ‰ increase) in bed 22–24 sediments concomitant with lower δ34S DBT values (−7 ‰ decrease), whereas co-eval δ34S KerS values remained relatively constant. The contrasting δ34S DBT and δ34S KerS data suggests the dynamic behavior of specific diagenetic sulfurisation processes may be resolved by the δ34S of discrete organic sulfur compounds (i.e., dibenzothiophenes, DBTs), but dissipated by the sulfurisation collective represented by the bulk kerogen fraction. The inverse isotopic trend observed between DBT and TRIS resulted in negative Δδ34S DBT-TRIS values identifying an organic sulfurisation pathway(s) with an unusual preference over pyrite (FeS 2) for the lighter stable sulfur isotope. A redox control of the δ34S DBTs and δ34S TRIS deviations in the bed 22–24 extinction interval was confirmed by coincident variation in TRIS/(TRIS + KerS) and pyrite (Py) and highly reactive (HR) iron ratios (Fe Py /Fe HR). The iron (Fe) speciation data indicated a transition to ferruginous conditions, ruling out Fe2+ limitation as a factor in the bias against 34S evident in DBT formation. The 34S depletion of the DBTs promoted by the ferruginous setting may arise from the rapid and irreversible reaction of organic substrates with labile sulfur anions (e.g. HS-) or be supported by an especially localised sediment–water depositional microenvironment. Our study highlights the potential of incorporating stable sulfur isotope analytics of reduced and organic sulfur phases, particularly of specific organic compounds, into a holistic assessment of the dynamic sulfur biochemical periods of Earth's past. [ABSTRACT FROM AUTHOR]

Given a graph G , let f G (n , m) be the minimal number k such that every k independent n -sets in G have a rainbow m -set. Let D (2) be the family of all graphs with maximum degree at most two. For t ≥ 3 , let C t be the cycle with vertex set [ 1 , t ] and edge set { 12 , 23 , ... , (t − 1) t , t 1 }. Aharoni et al. (2019) conjectured that (i) f G (n , n − 1) = n − 1 for all graphs G ∈ D (2) and (ii) f C t (n , n) = n for t ≥ 2 n + 1. Lv and Lu (2020) showed that the conjecture (ii) holds when t = 2 n + 1. In this article, we show that the conjecture (ii) holds for t ≥ 1 3 n 2 + 44 9 n. An ordered set I = (a 1 , a 2 , ... , a n) on C t is called a 2-jump independent n -set of C t if a i + 1 − a i = 2 (mod t) for any 1 ≤ i ≤ n − 1. We also show that a collection of 2-jump independent n -sets F of C t with | F | = n admits a rainbow independent n -set, i.e. (ii) holds if we restrict F on the family of 2-jump independent n -sets. Moreover, we prove that if the conjecture (ii) holds, then (i) holds for all graphs G ∈ D (2) with c e (G) ≤ 4 , where c e (G) is the number of components of G isomorphic to cycles of even lengths. [ABSTRACT FROM AUTHOR]

Let S n , 2 be the graph obtained by joining each vertex of K 2 to n − 2 isolated vertices, and let S n , 2 − be the graph obtained from S n , 2 by deleting an edge incident to a vertex of degree two. Recently, Zhai, Lin and Shu [20] showed that ρ (G) ≤ 1 + 4 m − 3 2 for any C 5 -free graph of size m ≥ 8 or C 6 -free graph of size m ≥ 22 , with equality if and only if G ≅ S m + 3 2 , 2 (possibly, with some isolated vertices). However, this bound is sharp only for odd m. Motivated by this, we want to obtain a sharp upper bound of ρ (G) for C 5 -free or C 6 -free graphs with m edges. In this paper, we prove that if G is a C 5 -free graph of even size m ≥ 14 or C 6 -free graph of even size m ≥ 74 , and G contains no isolated vertices, then ρ (G) ≤ ρ ˜ (m) , with equality if and only if G ≅ S m + 4 2 , 2 − , where ρ ˜ (m) is the largest root of x 4 − m x 2 − (m − 2) x + (m 2 − 1) = 0. [ABSTRACT FROM AUTHOR]

The vertex-arboricity v a (G) of a graph G is defined to be the minimum number of colors needed to color the vertices of G such that no cycle is monochromatic. The list vertex-arboricity v a l (G) is the list-coloring version of this concept. In this paper, we prove that every toroidal graph G with neither K 5 − (a K 5 missing at most one edge) nor 6-cycles satisfies v a l (G) ≤ 2. This will be best possible in the sense that forbidding only one of the two structures cannot guarantee its (list) vertex-arboricity being at most 2. [ABSTRACT FROM AUTHOR]

For any field F and polynomials f 2 , f 3 ∈ F [ x , y ] , let Γ F (f 2 , f 3) denote the bipartite graph with vertex partition P ∪ L , where P and L are two copies of F 3 , and (p 1 , p 2 , p 3) ∈ P is adjacent to [ l 1 , l 2 , l 3 ] ∈ L if and only if p 2 + l 2 = f 2 (p 1 , l 1) and p 3 + l 3 = f 3 (p 1 , l 1). The graph Γ 3 (F) = Γ F (x y , x y 2) is known to be of girth eight. When F = F q is a finite field of odd characteristic or F = F ∞ is an algebraically closed field of characteristic zero, the graph Γ 3 (F) is conjectured to be the unique one with girth at least eight among those Γ F (f 2 , f 3) up to isomorphism. This conjecture has been confirmed for the case that both f 2 , f 3 are monomials over F q , and for the case that at least one of f 2 , f 3 is a monomial over F ∞. If one of f 2 , f 3 ∈ F q [ x , y ] is a monomial, it has also been proved the existence of a positive integer M such that G = Γ F q M (f 2 , f 3) is isomorphic to Γ 3 (F q M ) provided G has girth at least eight. In this paper, these results are shown to be valid when the restriction on the polynomials f 2 , f 3 is relaxed further to that one of them is the product of two univariate polynomials. Furthermore, all of such polynomials f 2 , f 3 are characterized completely. [ABSTRACT FROM AUTHOR]

This paper investigates the dynamics of a directed acyclic neural network by edge adding control. We find that the local stability and Hopf bifurcation of the controlled network only depend on the size and intersection of directed cycles, instead of the number and position of the added edges. More specifically, if there is no cycle in the controlled network, the local dynamics of the network will remain unchanged and Hopf bifurcation will not occur even if the number of added edges is sufficient. However, if there exist cycles, then the network may undergo Hopf bifurcation. Our results show that the cycle structure is a necessary condition for the generation of Hopf bifurcation, and the bifurcation threshold is determined by the number, size, and intersection of cycles. Numerical experiments are provided to support the validity of the theory. [ABSTRACT FROM AUTHOR]

A graph G is (d 1 , d 2) -colorable if its vertices can be partitioned into two subsets V 1 and V 2 such that Δ (G [ V 1 ]) ≤ d 1 and Δ (G [ V 2 ]) ≤ d 2. Let G 5 denote the family of planar graphs with girth at least 5. In this paper, we prove that every graph in G 5 without adjacent 5-cycles is (1 , 6) -colorable. • This is a new result towards planar graphs with girth 5 and containing no adjacent 5-cycles. • The skill of discharging method in this paper is a powerful tool to solve the problem of this kind of coloring. • The discharging rulers are well designed. • Establish some reducible configurations by using clever skills. [ABSTRACT FROM AUTHOR]

An (F d 1 , F d 2 ) -partition of a graph G is a partition of V (G) into two subsets V 1 and V 2 such that G [ V i ] is a forest with maximum degree at most d i for i = 1 , 2. In this paper we show that every planar graph without 4-cycles and 6-cycles has an (F 5 , F 5) -partition. This improves a result by Huang, Huang and Lv in 2023, which says that G has an (F 2 , F) -partition. • We study the vertex-partition problem of graphs. • We give a (F 5 , F 5) -partition for a planar graph without 4- and 6-cycles. • We investigate the structural properties of planar graphs without 4- and 6-cycles. • We use discharging method to show the main conclusion. [ABSTRACT FROM AUTHOR]

Given two graphs H and F , the maximum possible number of copies of H in an F -free graph on n vertices is denoted by ex (n , H , F). Let ℓ ⋅ F denote ℓ vertex disjoint copies of F. Győri and Li (2012) obtained results on ex (n , C 3 , C 2 k + 1) , which was further improved by Alon and Shikhelman (2016). In this paper, we determine the exact value of ex (n , C 3 , ℓ ⋅ C 2 k + 1) and its extremal graph for all ℓ ≥ 2 and large n. [ABSTRACT FROM AUTHOR]

This paper is concerned with estimating the parameters of the modified Kies exponential (MKEx) distribution using the classical estimation method, based on ranked set sampling (RSS), Likelihood estimation method is used for estimating the MKEx parameters. The maximum likelihood estimators (MLEs) are then investigated and compared to the corresponding ones based on simple random sampling (SRS) and RSS designs. A Monte Carlo simulation is used to obtain the absolute relative biases, mean square errors for the MKEx distribution. Efficiencies are compared for the different designs. The relative efficiency of RSS design was found to increase with increasing the number of cycles, compared with other designs for the MKEx distribution. [ABSTRACT FROM AUTHOR]

Let P n be a path with n vertices. In this article, we use linear programming to obtain two sharp lower bounds for the optimal (1 , t) -pebbling number of P n and then determine the exact value if t is even or t = 1 or t ≥ ⌈ n 2 ⌉ − 1. [ABSTRACT FROM AUTHOR]

A coclique extension of a graph H is a graph G obtained from H by replacing each vertex of H by a coclique, where vertices of G coming from different vertices of H are adjacent if and only if the original vertices are adjacent in H. Let M n (H) be the set of graphs with order n , which are the coclique extensions of H. In this paper, we discuss the minimum spectral radius in M n (P k) and the maximum spectral radius in M n (C k) , where P k and C k are the path of order k and the cycle of order k , respectively. Then we disprove a conjecture on the minimum spectral radius in M n (P k) and confirm a conjecture on the maximum spectral radius in M n (C k) , which are given by Monsalve and Rada (2021) [4]. [ABSTRACT FROM AUTHOR]

In this paper we investigate the structure of flip graphs on non-crossing perfect matchings in the plane. Specifically, consider all non-crossing straight-line perfect matchings on a set of 2 n points that are placed equidistantly on the unit circle. A flip operation on such a matching replaces two matching edges that span an empty quadrilateral with the other two edges of the quadrilateral, and the flip is called centered if the quadrilateral contains the center of the unit circle. The graph G n has those matchings as vertices, and an edge between any two matchings that differ in a flip, and it is known to have many interesting properties. In this paper we focus on the spanning subgraph H n of G n obtained by taking all edges that correspond to centered flips, omitting edges that correspond to non-centered flips. We show that the graph H n is connected for odd n , but has exponentially many small connected components for even n , which we characterize and count via Catalan and generalized Narayana numbers. For odd n , we also prove that the diameter of H n is linear in n. Furthermore, we determine the minimum and maximum degrees of H n for all n , and characterize and count the corresponding vertices. Our results imply the non-existence of certain rainbow cycles in G n , and they resolve several open questions and conjectures raised in a recent paper by Felsner, Kleist, Mütze, and Sering. [ABSTRACT FROM AUTHOR]

In this paper we extend the study of three state lively quantum walks on cycles by considering the coin operator as linear sum of permutation matrices, which is a generalization of the Grover matrix. First we provide a complete characterization of orthogonal matrices of order 3 × 3 which are linear sum of permutation matrices. Consequently, we determine several groups of complex, real and rational orthogonal matrices. We establish that an orthogonal matrix of order 3 × 3 is a linear sum of permutation matrices if and only if it is permutative. Finally we determine period of lively quantum walk on cycles when the coin operator belongs to the orthogonal group of (real) linear sum of permutation matrices. [ABSTRACT FROM AUTHOR]

The connectivity is an important measurement for the fault-tolerance of networks. The structure connectivity and substructure connectivity are two generalizations of the classical connectivity. For a fixed graph H , a set F of subgraphs of G is called an H -structure cut (resp., H -substructure cut) of G , if G − ∪ F ∈ F V (F) is disconnected and every element of F is isomorphic to H (resp., a connected subgraph of H). The H -structure connectivity (resp., H -substructure connectivity) of G , denoted by κ (G ; H) (resp., κ s (G ; H)), is the cardinality of a minimal H -structure cut (resp., H -substructure cut) of G. In this paper, we will establish both κ (S n ; H) and κ s (S n , H) for every H ∈ { K 1 , K 1 , 1 , K 1 , 2 , ... , K 1 , n − 2 , P 4 , P 5 , C 6 } , where S n is the n -dimensional star graph. These results will show that star networks are highly tolerant of structure faults. [ABSTRACT FROM AUTHOR]

In 1975, P. Erdős proposed the problem of determining the maximum number f (n) of edges in a graph with n vertices in which any two cycles are of different lengths. The sequence (c 1 , c 2 , ... , c n) is the cycle length distribution of a graph G with n vertices, where c i is the number of cycles of length i in G. Let f (a 1 , a 2 , ... , a n) denote the maximum possible number of edges in a graph which satisfies c i ≤ a i , where a i is a nonnegative integer. In 1991, Shi posed the problem of determining f (a 1 , a 2 , ... , a n) which extended the problem due to Erdős. It is clear that f (n) = f (1 , 1 , ... , 1). Let g (n , m) = f (a 1 , a 2 , ... , a n) , where a i = 1 if i ∕ m is an integer, and a i = 0 otherwise. It is clear that f (n) = g (n , 1). We prove that lim inf n → ∞ f (n) − n n ≥ 2 + 40 99 , which is better than the previous bounds 2 (Shi (1988)), and 2 + 7654 19071 (Lai (2017)). We show that lim inf n → ∞ g (n , m) − n n m > 2. 444 , for all even integers m. We make the following conjecture: lim inf n → ∞ f (n) − n n > 2. 444. [ABSTRACT FROM AUTHOR]

A broadcast on a graph G = (V , E) is a function f : V ⟶ { 0 , ... , diam (G) } such that f (v) ≤ e G (v) for every vertex v ∈ V , where diam (G) denotes the diameter of G and e G (v) the eccentricity of v in G. The cost of such a broadcast is then the value ∑ v ∈ V f (v). Various types of broadcast functions on graphs have been considered in the literature, in relation with domination, irredundance, independence or packing, leading to the introduction of several broadcast numbers on graphs. In this paper, we determine these broadcast numbers for all paths and cycles, thus answering a question raised in Ahmadi et al. (2015). [ABSTRACT FROM AUTHOR]

A set S of vertices of a graph G is a defensive alliance of G if for every v ∈ S , it holds | N v ∩ S | ≥ | N v − S |. An alliance is g l o b a l if it is also a dominating set. The global defensive alliance number of G is the cardinality of a minimum global defensive alliance set of G. The lexicographic product of graphs G n = (V 1 , E 1) and H m = (V 2 , E 2) is the graph G = (V , E) , such that V = V 1 × V 2 and E = { (u 1 , u 2) (v 1 , v 2) : u 1 v 1 ∈ E 1 , or u 1 = v 1 and u 2 v 2 ∈ E 2 }. In this paper, we determine the global defensive alliance number of the lexicographic product of paths and cycles. [ABSTRACT FROM AUTHOR]

Reliability based criteria are quite popular for optimal sensor network design. We present a modified definition of system reliability for sensor network design for two applications: reliable estimation of variables in a steady state linear flow process, and reliable fault detection and diagnosis for any process. Unlike the weakest-link based definition of system reliability in the literature, the proposed definition considers the entire system and is consistent with the reliability concept used in classical reliability literature. For each application, dual approaches for defining system reliability are proposed, and their analogy with the reliability problem in the classical reliability literature is established. Using examples and stochastic simulations, the advantage of using the proposed system reliability in contrast to the existing definition is illustrated. Part II of this series of articles presents methods for efficient generation of the system reliability function and its use in optimization-based approaches for designing optimal sensor networks. • New definition of system reliability objective proposed for sensor network design. • Idea demonstrated for fault detection and diagnosis, and estimation of variables. • Dual approaches for system reliability computation proposed. • Analogies between proposed and classical reliability definitions presented. • Ideas demonstrated using illustrative and comparative studies. [ABSTRACT FROM AUTHOR]

Graph embedding is an important technique that maps a guest graph into a host graph, usually an interconnection network. Many applications can be modeled as graph embedding. In architecture simulation, graph embedding has been known as a powerful tool for implementation of parallel algorithms or simulation of different interconnection networks. The quality of an embedding can be measured by certain cost criteria. One of these criteria is the wirelength and has been well studied by many authors (Lai and Tsai, 2010 18 ; Fan and Jia, 2007 10 ; Han et al., 2010 15 ; Fang and Lai, 2005 11 ; Park and Chwa, 2000 23 ; Rajasingh et al., 2004; Yang et al., 2010; Yang, 2009 27 ; Manuel et al., 2009; Bezrukov et al., 1998; Rostami and Habibi, 2008 26 ; Choudum and Nahdini, 2004 7 ; Guu, 1997 14). In this paper, we compute the exact wirelength of embedding complete multipartite graphs into certain graphs, such as path, cycle, wheel, hypertree, cylinder, torus and 3-regular circulant graphs. [ABSTRACT FROM AUTHOR]

The n -dimensional folded hypercube F Q n interconnection network has been shown that it is bipartite for every odd n ≥ 3 , and which is non-bipartite for every even n ≥ 2. Let F 4 = { f 1 , f 2 , f 3 , f 4 } denote the faulty set of extreme vertices from any four cycle in F Q n. Then, we show that the fault-free cycles can be embedded in F Q n − F 4 as follows: 1. For n ≥ 3 , F Q n − F 4 contains a fault-free cycle of every even length from 4 to 2 n − 4 ; 2. For every even n ≥ 4 , F Q n − F 4 contains a fault-free cycle of every odd length from n + 1 to 2 n − 5. The results are optimal with respect to the length type of embedded cycles in F Q n − F 4. [ABSTRACT FROM AUTHOR]

A new variant of pebbling, " (d , t) -pebbling", was first proposed by Chang and Shiue in an article entitled by "An Investigation of the Game of Defend the Island". This type of pebbling is distance restricted. That is, the distance between any start vertex and a target vertex is at most d when we apply pebbling moves. It is easy to verify that the optimal (1 , 1) -pebbling number is equal to the Roman domination number for any graph. Hence, it is interesting to study the (d , t) -pebbling in graphs. In this article, we first obtain a lower bound of the optimal (d , t) -pebbling number for all regular graphs when d = 1 , 2 and then we determine the exact value of the optimal (1 , t) -pebbling number for all cycles and each positive integer t. [ABSTRACT FROM AUTHOR]

A spectral version of extremal graph theory problem is as follows: what is the maximum spectral radius of an H -free graph of order n ? Nikiforov posed a conjecture on spectral extremal value of cycles. In the past decade, much attention has been paid to this conjecture and other questions on spectral extremal graphs. In order to approach to Nikiforov's conjecture, we provide a new conjecture on spectral extremal value involving fans and wheels. Moreover, we show it is true for k = 2. [ABSTRACT FROM AUTHOR]

Lithium-ion batteries inevitably encounter vibration in practical applications, necessitating in-depth research on the impact of vibration on the electrochemical performance of batteries. This study investigates the alterations in the electrochemical performance of batteries subjected to vibration at different frequencies and the changes in cyclic batteries after vibration. The degradation mechanism of the battery during vibration and cycling is revealed through electrochemical characterization and post-mortem analysis. The results indicate a significant decrease in stored electric energy within the battery after vibration. The direct current internal resistance of the battery shows a minor increase, while the impedance of the solid electrolyte interface (SEI) and the charge transfer impedance slightly decrease after vibration. In addition, black stripes appear on the surface of the separator, and broken particles are observed on the anode surface. Compared to fresh batteries undergoing direct cycling, the cycling performance of the battery significantly deteriorates after vibration. The impedance at each stage exhibits a significant increase, and the IC peak exhibits a significant decrease and deviation. Vibration exacerbates the loss of lithium inventory (LLI) and active materials (LAM) during the cycling process of batteries. This study can provide guidance for enhancing the shock absorption design of batteries in practical applications. • Cyclic aging of batteries after vibration at different frequencies was performed. • Vibration exacerbates degradation during battery cycling. • The effect of vibration frequency on battery cycling performance is non-linear. • Loss of lithium ions and loss of active material are the main causes of battery aging. [ABSTRACT FROM AUTHOR]

[Display omitted] • In 2 lab experiments, 32 drivers viewed POV footage of cyclists in the road ahead. • They did so under no light, and static & flashing rear cycle light conditions. • A steady flashing light improved drivers' estimates of the distance to the cyclist. • Confidence in estimates was greater for all light conditions relative to no light. The optimal cycle light configuration for maximizing cyclists' conspicuity to drivers is not clear. Advances in sensor technology has led to the development of 'reactive' cycle lights that detect changes in the environment and consequently increase their flashing speed and brightness in risky situations – for example, when a rearward car is approaching – but no research has examined the effect of such lights on driver perception. The aim of the present study is to compare different cycle light configurations, including 'reactive' light technology, on drivers' ability to detect cyclists and estimate their proximity. We recruited 32 drivers to participate in two experiments, in which they viewed life-size real-world stimuli filmed from a driver's perspective in daytime and at dusk. The footage showed a cyclist on a bicycle with a rear light mounted on the seat post, in various configurations: static light , steady flashing , reactive flashing and no light. In Experiment 1, the drivers were required to detect the presence or absence of a cyclist on the road ahead as quickly as possible. In Experiment 2, they were required to estimate the distance of the cyclist from their vehicle, and to rate their confidence in their estimates. Experiment 1 revealed that drivers were quicker to detect the cyclist's presence in all rear cycle light conditions relative to the no light condition, but there were no differences in speed or accuracy across rear light conditions. Experiment 2 showed that drivers were more accurate in estimating the cyclist's proximity in the steady flashing and reactive flashing conditions, compared to static and no light conditions. Drivers were also more confident in their judgements in all rear light conditions compared to the no light condition. In conclusion, flashing rear cycle lights, regardless of reactive technology, enhanced drivers' perception of a cyclist ahead, notably in terms of their judgements of distance to that cyclist. Further investigation is needed to fully understand the impact of cycle light technology on driver perception, as well as the use of drivers' distance-to-cyclist estimates as an index of cyclists' cognitive conspicuity. [ABSTRACT FROM AUTHOR]

Rotation numbers for some maps of triods were introduced in [9]. The goal of this paper is to study patterns of triods which don't force other patterns with the same rotation number which we name triod twists. We obtain their complete characterization and show that these patterns can be conjugated to circle rotations by a piecewise monotone map. We also describe the dynamics of unimodal triod twist patterns with a given rational rotation number. [ABSTRACT FROM AUTHOR]

Assume k robots are placed on a cycle–the perimeter of a unit (radius) disk–at a position of our choosing and can move on the cycle with maximum speed one. A non-adversarial, uncooperative agent, called bus , is moving with constant speed s along the perimeter of the cycle. The robots are searching for the moving bus but do not know its exact location. Moreover, during the search they can move anywhere on the perimeter of the cycle. We give algorithms which minimize the worst-case search time required for at least one of the robots to find the bus. The following results are obtained for one robot. 1) If the robot knows the speed s of the bus but does not know its direction of movement then the optimal search time is shown to be exactly 2 π / s , if s ≥ 1 , 4 π / (s + 1) , if 1 / 3 ≤ s ≤ 1 , and 2 π / (1 − s) , if s ≤ 1 / 3. 2) If the robot does not know neither the speed nor the direction of movement of the bus then the optimal search time is shown to be 2 π (1 + 1 s + 1). Moreover, for all ϵ > 0 there exists a speed s such that any algorithm knowing neither the bus speed nor its direction will need time at least 4 π − ϵ to meet the bus. These results are also generalized to k ≥ 2 robots and analogous tight upper and lower bounds are proved depending on the knowledge the robots have about the speed and direction of movement of the bus. [ABSTRACT FROM AUTHOR]