Search

In this paper, we observe a special class of graphs known as multilayered graphs and their subclasses, namely multilayered cycles and multilayered paths. These graphs model layouts of shopping malls, city street grids, and even resemble the topology of certain famous board games. We analyze the values of all vertex spans (strong, direct, and Cartesian span) for these subclasses of graphs. Surprisingly, our results for multilayered cycles reveal that, regardless of the chosen movement rules, the span values depend solely on the length of the individual cycles, rather than the number of layers. This finding carries significant implications for the application of graph spans in maintaining safety distances. [ABSTRACT FROM AUTHOR]

The mathematical side of applied problems in multiple subject areas (biology, pattern recognition, etc.) is reduced to the problem of discrete optimization in the following mathematical method. We were provided a network and graphs in its leaves, for which we needed to find a rearrangement of graphs by non-leaf nodes, in which the given functional reached its minimum. Such a problem, even in the simplest case, is NP-hard, which means unavoidable restrictions on the network, on graphs, or on the functional. In this publication, this problem is addressed in the case of all graphs being so-called "structures", meaning directed-loaded graphs consisting of paths and cycles, and the functional as the sum (over all edges in the network) of distances between structures at the endpoints of every edge. The distance itself is equal to the minimal length of sequence from the fixed list of operations, the composition of which transforms the structure at one endpoint of the edge into the structure at its other endpoint. The list of operations (and their costs) on such a graph is fixed. Under these conditions, the given discrete optimization problem is called the reconstruction problem. This paper presents novel algorithms for solving the reconstruction problem, along with full proofs of their low error and low polynomial complexity. For example, for the network, the problem is solved with a zero error algorithm that has a linear polynomial computational complexity; and for the tree the problem is solved using an algorithm with a multiplicative error of at most two, which has a second order polynomial computational complexity. [ABSTRACT FROM AUTHOR]

A methodology is proposed for modifying computer ontologies (CO) for electronic courses (EC) in the field of information and communication technologies (ICT) for universities, schools, extracurricular institutions, as well as for the professional retraining of specialists. The methodology includes the modification of CO by representing the formal ontograph of CO in the form of a graph and using techniques for working with the graph to find optimal paths on the graph using applied software (SW). A genetic algorithm (GA) is involved in the search for the optimal CO. This will lead to the division of the ontograph into branches and the ability to calculate the best trajectory in a certain sense through the EC educational material, taking into account the syllabus. An example is considered for the ICT course syllabus in terms of a specific topic covering the design and use of databases. It is concluded that for the full implementation of this methodology, a tool is needed that automates this procedure for developing EC and/or electronic textbooks. An algorithm and a prototype of software tools are also proposed, integrating machine methods of working with CO and graphs. [ABSTRACT FROM AUTHOR]

A coalition in a graph G = (V;E) consists of two disjoint sets of vertices V1 and V2, neither of which is a dominating set of G but whose union V1 ∪ V2 is a dominating set of G. A coalition partition in a graph G of order n = |V | is a vertex partition π = {V1; V2, . . ., Vkg of V such that every set Vi either is a dominating set consisting of a single vertex of degree n - 1, or is not a dominating set but forms a coalition with another set Vj which is not a dominating set. Associated with every coalition partition &#960, of a graph G is a graph called the coalition graph of G with respect to &#960, denoted CG(G, &#960,), the vertices of which correspond one-to-one with the sets V1, V2, . . ., Vk of &#960, and two vertices are adjacent in CG(G, &#960,) if and only if their corresponding sets in &#960, form a coalition. In this paper we study coalition graphs, focusing on the coalition graphs of paths, cycles, and trees. We show that there are only finitely many coalition graphs of paths and finitely many coalition graphs of cycles and we identify precisely what they are. On the other hand, we show that there are infinitely many coalition graphs of trees and characterize this family of graphs. [ABSTRACT FROM AUTHOR]

The first entire Zagreb index (FEZI) is a graph parameter that has proven to be essential in various real-life scenarios, such as networking businesses and traffic management on roads. In this research paper, the FEZI was explored for a variety of fuzzy graphs, including star, firefly graph, cycle, path, fuzzy subgraph, vertex elimination, and edge elimination. This study presented several results, including determining the relationship between two isomorphic fuzzy graphs and between a path and cycle (connecting both end vertices of the path). This research also deals with the analysis of α -cut fuzzy graphs and establishes bounds for some fuzzy graphs. To apply these findings to modern life problems, the research team utilized the results to identify areas that require more development in internet systems. These results have practical implications for enhancing the efficiency and effectiveness of internet systems. The conclusion drawn from this research can be used to inform future research and aid in the development of more efficient and effective systems in various fields. [ABSTRACT FROM AUTHOR]

In view of the successful applications of graph theory, relationships between the biological activity and chemical structure have been developed. One of the popular topics in graph theory is problems relating to topological indices. Degree-based topological indices, distance-based topological indices, and counting-related topological indices are various types of topological indices. Physiochemical properties such as boiling point and stability of chemical compounds are correlated by these topological indices. A topological index of a graph is a numerical quantity obtained from the graph mathematically. A cactus graph is a connected graph in which no edge lies in more than one cycle. In this study, we have derived certain degree-based topological indices for some families of graphs consisting of graph obtained by the rooted product of paths and cycles and two types of cactus graph (paracactus and orthocactus) with the help of the generalized Zagreb index. [ABSTRACT FROM AUTHOR]

Let G be a graph. A 2-rainbow dominating function (or 2-RDF) of G is a function f from V (G) to the set of all subsets of the set f1; 2g such that for a vertex v 2 V (G) with f(v) =;, the condition S u2NG(v) f(u) = f1; 2g is fulfilled, where NG(v) is the open neighborhood of v. The weight of 2-RDF f of G is the value !(f):= P v2V (G) jf(v)j. The 2-rainbow domination number of G, denoted by r2(G), is the minimum weight of a 2-RDF of G. A 2-RDF f is called an outer independent 2-rainbow dominating function (or OI2-RDF) of G if the set of all v 2 V (G) with f(v) =; is an independent set. The outer independent 2-rainbow domination number oir2(G) is the minimum weight of an OI2-RDF of G. In this paper, we obtain the outer independent 2-rainbow domination number of PmPn and PmCn. Also we determine the value of oir2(Cm2Cn) when m or n is even. [ABSTRACT FROM AUTHOR]

Let G be either a complete graph of odd order or a complete bipartite graph in which each vertex partition has an even number of vertices. In this paper, we determine the set of triples (p, q, r), with p, q, r > 0, for which there exists a decomposition of G into p paths, q stars, and r cycles, each of which has 4 edges. [ABSTRACT FROM AUTHOR]

In any interconnection network, task allocation plays a major role in the processor speed as fair distribution leads to enhanced performance. Complete multipartite networks serve well for this purpose as the task can be split into different partites which improves the degree of reliability of the network. Such an allocation process in the network can be done by means of graph embedding. The optimal wirelength of a graph embedding helps in the distribution of deterministic algorithms from the guest graph to other host graphs in order to incorporate its unique deterministic properties on that chosen graph. In this paper, we propose an algorithm to compute the optimal wirelength of balanced complete multipartite graphs onto the Cartesian product of trees with path and cycle. Moreover, we derive the closed formulae for wirelengths in specific trees like (1-rooted) complete binary tree and sibling graphs. [ABSTRACT FROM AUTHOR]

The parity of the length of paths and cycles is a classical and well-studied topic in graph theory and theoretical computer science. The parity constraints can be extended to label constraints in a group-labeled graph, which is a directed graph with each arc labeled by an element of a group. Recently, paths and cycles in group-labeled graphs have been investigated, such as packing non-zero paths and cycles, where "non-zero" means that the identity element is a unique forbidden label. In this paper, we present a solution to finding an s – t path with two labels forbidden in a group-labeled graph. This also leads to an elementary solution to finding a zero s – t path in a Z 3 -labeled graph, which is the first nontrivial case of finding a zero path. This situation in fact generalizes the 2-disjoint paths problem in undirected graphs, which also motivates us to consider that setting. More precisely, we provide a polynomial-time algorithm for testing whether there are at most two possible labels of s – t paths in a group-labeled graph or not, and finding s – t paths attaining at least three distinct labels if exist. The algorithm is based on a necessary and sufficient condition for a group-labeled graph to have exactly two possible labels of s – t paths, which is the main technical contribution of this paper. [ABSTRACT FROM AUTHOR]

In the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for n-vertex bipartite graph of degree Δ ≤ 4 can be solved in O(n2) time. This extends Jansen's result [K. Jansen, The optimum cost chromatic partition problem, in: Proc. CIAC'97, Lecture Notes in Comput. Sci. 1203 (1997) 25-36] for paths and cycles to subgraphs of biquartic graphs. [ABSTRACT FROM AUTHOR]

Let H be a graph. A decomposition of H is a set of edge-disjoint sub- graphs of H whose union is H. A Hamiltonian path (respectively, cycle) of H is a path (respectively, cycle) that contains every vertex of H exactly once. A k-star, denoted by Sk, is a star with k edges. In this paper, we give necessary and sufficient conditions for decomposing the complete graph into α copies of Hamiltonian path (cycle) and β copies of S3. [ABSTRACT FROM AUTHOR]

A circulant-permutation-based spatially-coupled (SC) code is constructed by partitioning the circulant permutation matrices (CPMs) in the parity-check matrix of a block code into several components and piecing copies of these components in a diagonal structure. By connecting several SC codes, multi-dimensional SC (MD-SC) codes are constructed. In this paper, we present a systematic framework for constructing MD-SC codes with notably better cycle properties than their one-dimensional counterparts. In our framework, the multi-dimensional coupling is performed via an informed relocation of problematic CPMs. This work is general in the terms of the number of constituent SC codes that are connected together, the number of neighboring SC codes that each constituent SC code is connected to, and the length of the cycles whose populations we aim to reduce. Finally, we present a decoding algorithm that utilizes the structures of the MD-SC code to achieve lower decoding latency. Compared to the conventional SC codes, our MD-SC codes have a notably lower population of small cycles, and a dramatic BER improvement. The results of this work can be particularly beneficial in data storage systems, e.g., 2D magnetic recording and 3D Flash systems, as high-performance MD-SC codes are robust against various channel impairments and non-uniformity. [ABSTRACT FROM AUTHOR]

We consider subexponential algorithms finding weighted homomorphisms from intersection graphs of curves (string graphs) with n vertices to a fixed graph H. We provide a complete dichotomy: if H has no two vertices sharing two common neighbors, then the problem can be solved in time 2 O (n 2 / 3 log ⁡ n) , otherwise there is no subexponential algorithm, assuming the ETH. Then we consider locally constrained homomorphisms. We show that for each target graph H , the locally injective and locally bijective homomorphism problems can be solved in time 2 O (n log ⁡ n) in string graphs. For locally surjective homomorphisms we show a dichotomy for H being a path or a cycle. If H is P 3 or C 4 , then the problem can be solved in time 2 O (n 2 / 3 log 3 / 2 ⁡ n) in string graphs; otherwise, assuming the ETH, there is no subexponential algorithm. As corollaries, we obtain new results concerning the complexity of homomorphism problems in P t -free graphs. [ABSTRACT FROM AUTHOR]

We show that for each k ≥ 4 and n > r ≥ k + 1 , every n -vertex hypergraph with edge sizes at least r and no Berge cycle of length at least k has at most (k − 1) (n − 1) r edges. The bound is exact, and we describe the extremal hypergraphs. This implies and slightly refines the theorem of Győri, Katona and Lemons that for n > r ≥ k ≥ 3 , every n -vertex r -uniform hypergraph with no Berge path of length k has at most (k − 1) n r + 1 edges. To obtain the bounds, we study bipartite graphs with no cycles of length at least 2 k , and then translate the results into the language of multi-hypergraphs. [ABSTRACT FROM AUTHOR]

We consider the problem of inferring an edge-labeled graph from the sequence of edge labels seen in a walk on that graph. It has been known that this problem is solvable in O (n log ⁡ n) time when the targets are path or cycle graphs. This paper presents an online algorithm for the problem of this restricted case that runs in O (n) time, based on Manacher's algorithm for computing all the maximal palindromes in a string. [ABSTRACT FROM AUTHOR]

Alice wants to join a new social network, and influence its members to adopt a new product or idea. Each person v in the network has a certain threshold t (v) for activation , i.e. adoption of the product or idea. If v has at least t (v) activated neighbors, then v will also become activated. If Alice wants to make k new friends in the network, and thereby activate the most number of people, how should she choose these friends? We study the problem of choosing the k people in the network to befriend, who will in turn activate the maximum number of people. This Maximum Influence with Links Problem has applications in viral marketing and the study of epidemics. We show that the solution can be quite different from the related and widely studied influence maximization problem where the objective is to choose a seed or target set with maximum influence. We prove that the Maximum Influence with Links problem is NP-complete even for bipartite graphs in which all nodes have threshold 1 or 2. In contrast, we give polynomial time algorithms that find optimal solutions for the problem for trees, paths, cycles, and cliques. [ABSTRACT FROM AUTHOR]

Let Γ = (G, σ) be a signed graph, where G is the underlying simple graph and σ : E(G) → {--, +} is the sign function on the edges of G. The adjacency matrix of a signed graph has -1 or +1 for adjacent vertices, depending on the sign of the edges. It was conjectured that if Γ is a signed complete graph of order n with k negative edges, k < n -- 1 and Γ has maximum index, then negative edges form K1,k. In this paper, we prove this conjecture if we confine ourselves to all signed complete graphs of order n whose negative edges form a tree of order k + 1. A [1, 2]-subgraph of G is a graph whose components are paths and cycles. Let Γ be a signed complete graph whose negative edges form a [1, 2]-subgraph. We show that the eigenvalues of Γ satisfy the following inequalities: --5 ≤ λn ≤ ... ≤ λ2 ≤ 3. [ABSTRACT FROM AUTHOR]

Coloring the vertices of a particular graph has often been motivated by its utility to various applied fields and its mathematical interest. A dynamic coloring of a graph G is a proper coloring of the vertex set V(G) such that for each vertex of degree at least 2, its neighbors receive at least two distinct colors. A dynamic k-coloring of a graph is a dynamic coloring with k colors. A dynamic k-coloring is also called a conditional (k, 2)-coloring. The smallest integer k such that G has a dynamic k-coloring is called the dynamic chromatic number χ d (G) of G. In this paper, we investigate the dynamic chromatic number for the line graph of sunlet graph and middle graph, total graph and central graph of sunlet graphs, paths and cycles. Also, we find the dynamic chromatic number for Mycielskian of paths and cycles and the join graph of paths and cycles. [ABSTRACT FROM AUTHOR]

A mixed graph is obtained from a graph by orienting some of its edges. The Hermitian adjacency matrix of a mixed graph with the vertex set { v 1 , ... , v n } , is the matrix H = h i j n × n , where h i j = − h j i = i if there is a directed edge from v i to v j , h i j = 1 if there exists an undirected edge between v i and v j , and h i j = 0 otherwise. The Hermitian spectrum of a mixed graph is defined to be the spectrum of its Hermitian adjacency matrix. In this paper we study mixed graphs which are determined by their Hermitian spectrum (DHS). First, we show that each mixed cycle is switching equivalent to either a mixed cycle with no directed edges (C n), a mixed cycle with exactly one directed edge (C n 1), or a mixed cycle with exactly two consecutive directed edges with the same direction (C n 2) and we determine the spectrum of these three types of cycles. Next, we characterize all DHS mixed paths and mixed cycles. We show that all mixed paths of even order, except P 8 and P 14 , are DHS. It is also shown that mixed paths of odd order, except P 3 , are not DHS. Also, all cospectral mates of P 8 , P 14 and P 4 k + 1 and two families of cospectral mates of P 4 k + 3 , where k ≥ 1 , are introduced. Finally, we show that the mixed cycles C 2 k and C 2 k 2 , where k ≥ 3 , are not DHS, but the mixed cycles C 4 , C 4 2 , C 2 k + 1 , C 2 k + 1 2 , C 2 k + 1 1 and C 2 j 1 except C 7 1 , C 9 1 , C 12 1 and C 15 1 , are DHS, where k ≥ 1 and j ≥ 2. [ABSTRACT FROM AUTHOR]

Using discrete Morse theory, we give an algorithm that prunes the excess of information in the Taylor resolution and constructs a new cellular free resolution for an arbitrary monomial ideal. The pruned resolution is not simplicial in general, but we can slightly modify our algorithm in order to obtain a simplicial resolution. We also show that the Lyubeznik resolution fits into our pruning strategy. The pruned resolution is not always minimal but it is a lot closer to the minimal resolution than the Taylor and the Lyubeznik resolutions as we will see in some examples. We finally use our methods to give a different approach to the theory of splitting of monomial ideals. We deduce from this splitting strategy that the pruned resolution is always minimal in the case of edge ideals of paths and cycles. [ABSTRACT FROM AUTHOR]

Background: Long-read sequencing has shown the promises to overcome the short length limitations of second-generation sequencing by providing more complete assembly. However, the computation of the long sequencing reads is challenged by their higher error rates (e.g., 13% vs. 1%) and higher cost ($0.3 vs. $0.03 per Mbp) compared to the short reads. Methods: In this paper, we present a new hybrid error correction tool, called ParLECH (Parallel Long-read Error Correction using Hybrid methodology). The error correction algorithm of ParLECH is distributed in nature and efficiently utilizes the k-mer coverage information of high throughput Illumina short-read sequences to rectify the PacBio long-read sequences.ParLECH first constructs a de Bruijn graph from the short reads, and then replaces the indel error regions of the long reads with their corresponding widest path (or maximum min-coverage path) in the short read-based de Bruijn graph. ParLECH then utilizes the k-mer coverage information of the short reads to divide each long read into a sequence of low and high coverage regions, followed by a majority voting to rectify each substituted error base. Results: ParLECH outperforms latest state-of-the-art hybrid error correction methods on real PacBio datasets. Our experimental evaluation results demonstrate that ParLECH can correct large-scale real-world datasets in an accurate and scalable manner. ParLECH can correct the indel errors of human genome PacBio long reads (312 GB) with Illumina short reads (452 GB) in less than 29 h using 128 compute nodes. ParLECH can align more than 92% bases of an E. coli PacBio dataset with the reference genome, proving its accuracy. Conclusion: ParLECH can scale to over terabytes of sequencing data using hundreds of computing nodes. The proposed hybrid error correction methodology is novel and rectifies both indel and substitution errors present in the original long reads or newly introduced by the short reads. [ABSTRACT FROM AUTHOR]

A star coloring of a graph G is a proper vertex coloring in which every path on four vertices in G is not bicolored. The star chromatic number Xs (G) ofG is the least number of colors needed to star color G. In this paper, we have generalized the star chromatic number of degree splitting of join of any two graph G and H denoted by G + H, where G is a path graph and H is any simple graph. Also, we determine the star chromatic number for degree splitting of join of path graph G of order m with path Pn, complete graph Kn and cyclevgraph Cn. [ABSTRACT FROM AUTHOR]

Graph coloring is an assignment of labels called colors to elements of a graph. The packing coloring was introduced by Goddard et al. [1] in 2008 which is a kind of coloring of a graph. This problem is NP-complete for general graphs. In this paper, we consider some transformation graphs and generalized their packing chromatic numbers. [ABSTRACT FROM AUTHOR]

Motivated by anti-Ramsey numbers introduced by Erdős, Simonovits and Sós in 1975, we study the anti-Ramsey problem when host graphs are plane triangulations. Given a positive integer n and a planar graph H , let T n (H) be the family of all plane triangulations T on n vertices such that T contains a subgraph isomorphic to H. The planar anti-Ramsey number of H , denoted a r P (n , H) , is the maximum number of colors in an edge-coloring of a plane triangulation T ∈ T n (H) such that T contains no rainbow copy of H. Analogously to anti-Ramsey numbers and Turán numbers, planar anti-Ramsey numbers are closely related to planar Turán numbers, where the planar Turán number of H is the maximum number of edges of a planar graph on n vertices without containing H as a subgraph. The study of a r P (n , H) (under the name of rainbow numbers) was initiated by Horňák et al. (2015). In this paper we study planar anti-Ramsey numbers for paths and cycles. We first improve existing lower bound for a r P (n , C k) when k ≥ 5 and n ≥ k 2 − k. Then, using the main ideas in the above-mentioned paper, we obtain upper bounds for a r P (n , C 6) when n ≥ 8 and a r P (n , C 7) when n ≥ 13 , respectively. Finally, we establish lower bounds for a r P (n , P k) when n ≥ k ≥ 8. [ABSTRACT FROM AUTHOR]

We construct a model for B (∞) using the alcove path model of Lenart and Postnikov. We show that the continuous limit of our model recovers a dual version of the Littelmann path model for B (∞) given by Li and Zhang. Furthermore, we consider the dual version of the alcove path model and obtain analogous results for the dual model, where the continuous limit gives the Li and Zhang model. [ABSTRACT FROM AUTHOR]

Fractional revival is a quantum transport phenomenon important for entanglement generation in spin networks. This takes place whenever a continuous-time quantum walk maps the characteristic vector of a vertex to a superposition of the characteristic vectors of a subset of vertices containing the initial vertex. A main focus will be on the case when the subset has two vertices. We explore necessary and sufficient spectral conditions for graphs to exhibit fractional revival. This provides a characterization of fractional revival in paths and cycles. Our work builds upon the algebraic machinery developed for related quantum transport phenomena such as state transfer and mixing, and it reveals a fundamental connection between them. [ABSTRACT FROM AUTHOR]

The eccentricity matrix E (G) of a graph G is derived from the distance matrix by keeping for each row and each column only the eccentricities. The E -eigenvalues of a graph G are those of its eccentricity matrix E (G) , and the eccentricity energy (or the E -energy) of G is the sum of the absolute values of E -eigenvalues. A graph is called self-centered graph if its diameter and radius are equal. In this paper, we investigate the relation between the E -energy and the ordinary energy, and we determine the exact values of E -energies of paths, cycles and double stars. Moreover, when G is an r -antipodal graph, we show that the E -energy of strong product of graphs G and H only depends on the structure of G. We finally provide upper and lower bounds for the E -energy whose extreme graphs are kinds of self-centered graphs, and we propose some potential topics for further study. [ABSTRACT FROM AUTHOR]

There have been extensive researchs on cycles in regular graphs, partic- ularly 3-connected cubic graphs. Generalized Petersen graphs, denoted by GP(n,k), are highly symmetric 3-connected cubic graphs, which have attracted great atten- tion. The Hamiltonicity of GP(n,k) has been studied for a long time and thoroughly settled. Inspired by Bondy's meta-conjecture that almost every nontrivial condition for Hamiltonicity also implies pancyclicity, we seek for more cycle structures in this class of graphs, by figuring out the possible lengths of cycles in them. It turns out that generalized Petersen graphs, though not generally pancyclic, miss only very few possible length of cycles. For k 2 f2,3g, we completely determine all possible cycle lengths in GP(n,k). We also obtain some results for GP(n,k) where k is odd. In particular, when k is odd, and n is even and suficiently large, GP(n,k) is bipartite and weakly even pancyclic. [ABSTRACT FROM AUTHOR]

The study of conditions on vertex degrees in a host graph G for the appearance of a target graph H is a major theme in extremal graph theory. The kth power of a graph F is obtained from F by joining any two vertices at distance at most k. We study minimum degree conditions under which a graph G contains the kth power of cycles and paths of arbitrary specified lengths. We determine precise thresholds, assuming that the order of G is large. This extends a result of Allen, Böttcher and Hladkfy concerning the containment of squared paths and squared cycles of arbitrary specified lengths and settles a conjecture of theirs in the affirmative. [ABSTRACT FROM AUTHOR]

We introduce the Turán problem for edge ordered graphs. We call a simple graph edge ordered, if its edges are linearly ordered. An isomorphism between edge ordered graphs must respect the edge order. A subgraph of an edge ordered graph is itself an edge ordered graph with the induced edge order. We say that an edge ordered graph G avoids another edge ordered graph H, if no subgraph of G is isomorphic to H. The Turán number ex0 <(n;H) of a family H of edge ordered graphs is the maximum number of edges in an edge ordered graph on n vertices that avoids all elements of H. We examine this parameter in general and also for several singleton families of edge orders of certain small specific graphs, like star forests, short paths and the cycle of length four. [ABSTRACT FROM AUTHOR]

Let k be a positive integer. We compute depth and Stanley depth of the quotient ring of the edge ideal associated to the kth power of a path on n vertices. We show that both depth and Stanley depth have the same values and can be given in terms of k and n. If n ≡ 0, k + 1, k + 2,..., 2k(mod(2k + 1)), then we give values of depth and Stanley depth of the quotient ring of the edge ideal associated to the kth power of a cycle on n vertices and tight bounds otherwise, in terms of n and k. We also compute lower bounds for the Stanley depth of the edge ideals associated to the kth power of a path and a cycle and prove a conjecture of Herzog for these ideals. [ABSTRACT FROM AUTHOR]

The bubble-sort graph B n is one of attractive underlying topologies for distributed systems. Let H be a certain connected subgraph of B n. The H -structure connectivity of B n , denoted κ (B n ; H) , is the cardinality of a minimal set of subgraphs F = { H 1 , H 2 , ... , H m } in B n , such that every H i ∈ F is isomorphic to H , and F 's removal will disconnect B n. The H -substructure connectivity of B n , denoted κ s (B n ; H) , is the cardinality of a minimal set of subgraphs F = { J 1 , J 2 , ... , J m } , such that every J i ∈ F is isomorphic to a connected subgraph of H , and F 's removal will disconnect B n. The two kinds of connectivity are both generalizations of the classic connectivity. In this paper, we prove that κ (B n ; P k) = κ s (B n ; P k) = ⌈ 2 (n − 1) k + 1 ⌉ for n ≥ 6 and odd k ≤ 2 n − 3 , κ (B n ; P k) = κ s (B n ; P k) = ⌈ 2 (n − 1) k ⌉ for n ≥ 6 and even k ≤ 2 n − 2 , and κ (B n ; C 2 k) = κ s (B n ; C 2 k) = ⌈ n − 1 k ⌉ for 6 ≤ 2 k ≤ n − 1. [ABSTRACT FROM AUTHOR]

The n -dimensional balanced hypercube B H n (n ≥ 1) has been proved to be a bipartite graph. Let P be a set of edges in B H n. For any two vertices u , v from different partite sets of V (B H n). In this paper, we prove that if | P | ≤ 2 n − 2 and the subgraph induced by P has neither u nor v as internal vertices , or both of u and v as end-vertices, then B H n contains a Hamiltonian path joining u and v passing through every edge of P if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths. As a corollary, if | P | ≤ 2 n − 1 , then B H n contains a Hamiltonian cycle passing through every edge of P if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths. [ABSTRACT FROM AUTHOR]

The Szeged index is a modification of the Wiener index to cyclic molecules. The Szeged index of a connected graph G is defined as SZ(G)= Σe∈E(G) n1(e|G)n2(e|G), where E(G) is the edge set of G, and for any e = uν ∈ E(G), n1(e|G) is the number of vertices of G lying closer to vertex u than to vertex ν, and n2(e|G) is the number of vertices of G lying closer to vertex ν than to vertex u. In this paper, we determine the n-vertex unicyclic graphs whose vertices on the unique cycle have degree at least three with the first, the second and the third smallest as well as largest Szeged indices for n ≥ 6, n ≥ 7 and n ≥ 8, respectively. [ABSTRACT FROM AUTHOR]

Abstract The graph of a Hecke operator encodes all information about the action of this operator on automorphic forms. Let X be a curve over F q , F its function field and A the adele ring of F. In this paper we will exhibit the first properties for the graph of Hecke operators for GL n (A) , for every n ≥ 1. This includes a description of the graph in terms of coherent sheaves on X. We provide a numerical condition for two vertices to be connected by an edge. Moreover, we describe how to calculate these graphs in the case of the projective line X = P 1 (F q). [ABSTRACT FROM AUTHOR]

Abstract The Frobenius–Perron dimension for an abelian category was recently introduced in [5]. We apply this theory to the category of representations of the finite-dimensional radical square zero algebras associated to certain modified ADE graphs. In particular, we take an ADE quiver with arrows in a certain orientation and an arbitrary number of loops at each vertex. We show that the Frobenius–Perron dimension of this category is equal to the maximum number of loops at a vertex. Along the way, we introduce a result which can be applied in general to calculate the Frobenius–Perron dimension of a radical square zero bound quiver algebra. We use this result to introduce a family of abelian categories which produce arbitrarily large irrational Frobenius–Perron dimensions. [ABSTRACT FROM AUTHOR]

A star edge-coloring of a graph G is a proper edge-coloring without 2-colored paths and cycles of length 4. For a graph G , let the list star chromatic index of G be the minimum k such that for any k -uniform list assignment L for the set of edges, G has a star edge-coloring from L. In this paper we prove that the list star chromatic index of every k -degenerate graph G with maximum degree Δ is at most (3 k − 2) Δ − k 2 + 2. For K 4 -minor free graphs (k = 2), we decrease this bound to 3 Δ − 3 , Δ ≥ 3. We do not use the discharging method but rather we use the fundamental structural properties of k -degenerate graphs and K 4 -minor free graphs. [ABSTRACT FROM AUTHOR]

Let P k be a path, C k a cycle on k vertices, and K k , k a complete bipartite graph with k vertices on each side of the bipartition. We prove that (1) for any integers k , t > 0 and a graph H there are finitely many subgraph minimal graphs with no induced P k and K t , t that are not H -colorable and (2) for any integer k > 4 there are finitely many subgraph minimal graphs with no induced P k that are not C k − 2 -colorable. The former generalizes the result of Hell and Huang (2013) and the latter extends a result of Bruce etal. (2009). Both our results lead to polynomial-time certifying algorithms for the corresponding coloring problems. [ABSTRACT FROM AUTHOR]

Abstract We study several problems related to graph modification under connectivity constraints from the perspective of parameterized complexity. In particular, we study (a) (Weighted) Biconnectivity Deletion, where we are tasked with deleting k edges while preserving biconnectivity in an undirected graph, and (b) Path-contraction Preserving Strong Connectivity, where we want to maintain strong connectivity of a digraph while path-contracting k arcs. The parameterized tractability of this last problem was posed in Bang-Jensen and Yeo (2008) [1] as an open question and we answer it here in the negative. On the other hand, we show that preserving (weighted) biconnectivity is fixed-parameter tractable (FPT) and the unweighted case even admits a randomized polynomial kernel. Finally, we show that the most general case of the (unweighted) problem where one would like to preserve ρ -vertex connectivity for any ρ is (non-uniformly) FPT parameterized by k and ρ. [ABSTRACT FROM AUTHOR]

Highlights • Improved underwater glider path planning mission scenarios optimization with L-SHADE. • New proposed algorithm yielded stable and competitive output trajectories. • Outranked all other previous results from literature and ranked first in comparison. • Several configured algorithms are also compared to, analysed, and further improved. Abstract This paper presents an application of a recently well performing evolutionary algorithm for continuous numerical optimization, Success-History Based Adaptive Differential Evolution Algorithm (SHADE) including Linear population size reduction (L-SHADE), to an expert system for underwater glider path planning (UGPP). The proposed algorithm is compared to other similar algorithms and also to results from literature. The motivation of this work is to provide an alternative to the current glider mission control systems, that are based mostly on multidisciplinary human-expert teams from robotic and oceanographic areas. Initially configured as a decision-support expert system, the natural evolution of the tool is targeting higher autonomy levels. To assess the performance of the applied optimizers, the test functions for UGPP are utilized as defined in literature, which simulate real-life oceanic mission scenarios. Based on these test functions, in this paper, the performance of the proposed application of L-SHADE to UGPP is aggregated using statistical analyis. The depicted fitness convergence graphs, final obtained fitness plots, trajectories drawn, and per-scenario analysis show that the new proposed algorithm yields stable and competitive output trajectories. Over the set of benchmark missions, the newly obtained results with a configured L-SHADE outperforms existing literature results in UGPP and ranks best over the compared algorithms. Moreover, some additional previously applied algorithms have been reconfigured to yield improved performance. Thereby, this new application of evolutionary algorithms to UGPP contributes significantly to the capacity of the decision-makers, when they use the improved UGPP expert system yielding better trajectories. [ABSTRACT FROM AUTHOR]

Abstract Given a fixed graph H , we provide a sharp degree-sum condition such that if a graph G is sufficiently large with sufficiently large minimum degree sum, then it contains a spanning H -subdivision in which the ground vertices and lengths of the corresponding edge paths are specified. [ABSTRACT FROM AUTHOR]

Abstract We consider the class of Berge graphs that do not contain an induced cycle of length four. We present a purely graph-theoretical algorithm that produces an optimal coloring in polynomial time for every graph in that class. [ABSTRACT FROM AUTHOR]

Abstract It was independently conjectured by Häggkvist in 1989 and Kriesell in 2011 that given a positive integer ℓ , every simple Eulerian graph with high minimum degree (depending on ℓ) admits an Eulerian tour such that every segment of length at most ℓ of the tour is a path. Bensmail, Harutyunyan, Le and Thomassé recently verified the conjecture for 4-edge-connected Eulerian graphs. Building on that proof, we prove here the full statement of the conjecture. This implies a variant of the path case of Barát–Thomassen conjecture that any simple Eulerian graph with high minimum degree can be decomposed into paths of fixed length and possibly an additional shorter path. [ABSTRACT FROM AUTHOR]

Abstract Given k pairs of vertices (s i , t i) (1 ≤ i ≤ k) of a digraph G , how can we test whether there exist vertex-disjoint directed paths from s i to t i for 1 ≤ i ≤ k ? This is NP-complete in general digraphs, even for k = 2 [4] , but in [3] we proved that for all fixed k , there is a polynomial-time algorithm to solve the problem if G is a tournament (or more generally, a semicomplete digraph). Here we prove that for all fixed k there is a polynomial-time algorithm to solve the problem when V (G) is partitioned into a bounded number of sets each inducing a semicomplete digraph (and we are given the partition). [ABSTRACT FROM AUTHOR]

Abstract Tetravalent graphs admitting a half-arc-transitive group of automorphisms, that is a subgroup of the automorphism group acting transitively on its vertices and its edges but not on its arcs, are investigated. One of the most fruitful approaches for the study of structural properties of such graphs is the well-known concept of alternating cycles and their intersections which was introduced by Marušič 20 years ago. In this paper a new parameter for such graphs, giving a further insight into their structure, is introduced. Various properties of this parameter are given and the parameter is completely determined for the tightly attached examples in which any two non-disjoint alternating cycles meet in half of their vertices. Moreover, the obtained results are used to establish a link between two frameworks for a systematic study of all tetravalent graphs admitting a half-arc-transitive group of automorphisms, namely the one proposed by Marušič and Praeger in 1999, and the much more recent one proposed by Al-bar, Al-kenai, Muthana, Praeger and Spiga which is based on the normal quotients method. New results on the graph of alternating cycles of a tetravalent graph admitting a half-arc-transitive group of automorphisms are obtained. A considerable step towards the complete answer to the question of whether the attachment number necessarily divides the radius in tetravalent half-arc-transitive graphs is made. A number of questions and open problems are posed. [ABSTRACT FROM AUTHOR]

Abstract We show that every 2-connected cubic graph G has a cycle double cover if G has a spanning subgraph F such that (i) every component of F has an even number of vertices (ii) every component of F is either a cycle or a subdivision of a Kotzig graph and (iii) the components of F are connected to each other in a certain general manner. [ABSTRACT FROM AUTHOR]

Abstract We prove that a complete multipartite graph K with n > 1 vertices and m edges can be decomposed into edge-disjoint Hamilton paths if and only if m n − 1 is an integer and the maximum degree of K is at most 2 m n − 1. [ABSTRACT FROM AUTHOR]