Search

Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit "natural" guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF formula on m clauses, there is an assignment that satisfies at least m/2 clauses. How difficult is it to decide whether there is an assignment satisfying more than m / 2 + k clauses? Or, if an n-vertex graph has a perfect matching, then its vertex cover is at least n/2. Is there a vertex cover of size at least n / 2 + k for some k ≥ 1 and how difficult is it to find such a vertex cover? The above guarantee paradigm has led to several exciting discoveries in the areas of parameterized algorithms and kernelization. We argue that this paradigm could bring forth fresh perspectives on well-studied problems in approximation algorithms. Our example is the longest cycle problem. One of the oldest results in extremal combinatorics is the celebrated Dirac's theorem from 1952. Dirac's theorem provides the following guarantee on the length of the longest cycle: for every 2-connected n-vertex graph G with minimum degree δ (G) ≤ n / 2 , the length of a longest cycle L is at least 2 δ (G) . Thus the "essential" part in finding the longest cycle is in approximating the "offset" k = L - 2 δ (G) . The main result of this paper is the above-guarantee approximation theorem for k. Informally, the theorem says that approximating the offset k is not harder than approximating the total length L of a cycle. In other words, for any (reasonably well-behaved) function f, a polynomial time algorithm constructing a cycle of length f(L) in an undirected graph with a cycle of length L, yields a polynomial time algorithm constructing a cycle of length 2 δ (G) + Ω (f (k)) . [ABSTRACT FROM AUTHOR]

For a poset P = (X , ≤ P) , the strict-double-bound graph (sDB (P)) of P = (X , ≤ P) is the graph with the vertex set X such that u v ∈ E (sDB (P)) if and only if u ≠ v and there exist x ∈ X and y ∈ X distinct from u and v such that x ≤ P u ≤ P y and x ≤ P v ≤ P y. For a connected graph G , the strict-double-bound number ζ (G) is defined as min { l : there exists a poset P such that sDB(P) ≅ G ∪ N l } , where N l is the graph with l vertices and no edges. In this paper we deal with the strict-double-bound numbers of Cartesian products of graphs. We show that ζ (P n × P m) ≤ 2 n + 2 m − 4 for n , m ≥ 2 , ζ (C 4 n × C 4 m) ≤ 8 n m + 4 for n , m ≥ 1 , and ζ (C n × C m) ≤ 4 n + 4 m − 4 for n , m ≥ 3. [ABSTRACT FROM AUTHOR]

In this paper. A new definition of discrete topological graph is introduced. Some properties of this graph are proved. If n > 2 are evaluated Gτ has no pendant vertex, not tree, also the value of the diameter and the minimum degree of Gτ . If n ≥ 2, Gτ has (2n − 3) complete bipartite induced subgraphs, Gτ is connected graph, simple graph, has no odd cycle, the clique number also proved, the value of the radius, the maximum degree and the chromatic number of Gτ have been studied. [ABSTRACT FROM AUTHOR]

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]

One of the well-known NP-hard optimization problems in graph theory is finding the longest path in a graph. This problem remains NP-hard for general grid graphs, and its complexity is open for grid graphs that have a limited number of holes. In this paper, we study this problem for odd-sized O -shaped grid graphs, i.e. a rectangular grid graph with a rectangular hole. We show that this problem can be solved in linear time. [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]

Let us say a graph is O s -free , where s ≥ 1 is an integer, if there do not exist s cycles of the graph that are pairwise vertex-disjoint and have no edges joining them. The structure of such graphs, even when s = 2 , is not well understood. For instance, until now we did not know how to test whether a graph is O 2 -free in polynomial time; and there was an open conjecture, due to Ngoc Khang Le, that O 2 -free graphs have only a polynomial number of induced paths. In this paper we prove Le's conjecture; indeed, we will show that for all s ≥ 1 , there exists c > 0 such that every O s -free graph G has at most | G | c induced paths, where | G | is the number of vertices. This provides a poly-time algorithm to test if a graph is O s -free, for all fixed s. The proof has three parts. First, there is a short and beautiful proof, due to Le, that reduces the question to proving the same thing for graphs with no cycles of length four. Second, there is a recent result of Bonamy, Bonnet, Déprés, Esperet, Geniet, Hilaire, Thomassé and Wesolek, that in every O s -free graph G with no cycle of length four, there is a set of vertices that intersects every cycle, with size logarithmic in | G |. And third, there is an argument that uses the result of Bonamy et al. to deduce the theorem. The last is the main content of this paper. [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]

A sum divisor cordial labeling (SDCL) of a graph G+ with node set V is bijective. T from V to f1; 2; 3;: :: ; jV (G)jg in such a way that if each edge xy is reserved the label 1 if 2j[T(x) + T(y)] and 0 otherwise, then the number of edges labeled with 0 and the number of edges labeled with 1 under the condition jeT(0) eT(1)j 1. A graph with a sum divisor cordial labeling (SDCL) is called a sum divisor cordial graph (SDCG). Thus, by using the above properties here we investigate that path union of two copies of cycle, cycle with triangle, wheel, helm, closed helm admit sum divisor cordial labeling. [ABSTRACT FROM AUTHOR]

In this paper we introduce the notion of congruence for regions in lattice path models. This turns out to be useful for deriving a path counting formula for the auxiliary lattice path model in the presence of long steps, source and target points of which are situated near the filter restrictions. This problem was motivated by the fact, that weighted numbers of paths in such model mimic multiplicities in tensor power decomposition of Uq(sl2)-module T(1)⊗N at roots of unity. We expand on combinatorial properties of such model and introduce the punchline of a proof for explicit path counting formula. [ABSTRACT FROM AUTHOR]

Carsten Thomassen in 1989 conjectured that if a graph has minimum degree much more than the number of atoms in the universe (δ (G) ≥ 10 10 10 ), then it contains a pillar , which is a graph that consists of two vertex-disjoint cycles of the same length, s say, along with s vertex-disjoint paths of the same length3 which connect matching vertices in order around the cycles. Despite the simplicity of the structure of pillars and various developments of powerful embedding methods for paths and cycles in the past three decades, this innocent looking conjecture has seen no progress to date. In this paper, we give a proof of this conjecture by building a pillar (algorithmically) in sublinear expanders. [ABSTRACT FROM AUTHOR]

In 1966 Gallai asked the following question: Do all longest paths (cycles) of a connected graph contain a common vertex? After a positive answer to Gallai's question, another question has been raised, Is there any family of graphs without Gallai's property? Menke found one such family, the square lattices. Embedding methods hold the promise to transform not just the way calculations are performed, but to significantly reduce computational costs and often used in quantum mechanics and material sciences. In this paper, we prove the existence of graphs with the empty intersection of their longest cycles as subgraphs of Archimedean lattices. [ABSTRACT FROM AUTHOR]

This paper demonstrates a new way of seeing and theorizing about the dynamics of organizational routines through the concept of paths—time-ordered sequences of actions or events in performing work. Empirically and conceptually, paths provide the missing link between specific actions and patterns of action. When routines are represented as a narrative network, tracing the formation and dissolution of action paths can generate new insights about the dynamic patterning of actions in routine performances. We traced action paths using longitudinal field data from a videogame development project, and found that action patterns change dramatically over time based on the needs of the project. We explain these changes in terms of generic mechanisms that lead to the enactment of more (or fewer) paths in the narrative network. We propose that patterning can be seen as a new motor of routine dynamics and discuss generic mechanisms through which patterning can influence narrative network structure. [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]

Let G be a finite simple graph and let A(G) be its adjacency matrix. Then G is singular if A(G) is singular. Suppose Pb1, Pb2, Pb3 are three paths with disjoint vertices, where bi > 2(i = 1,2,3), and at most one of them is 2. Coalescing together one of the two end vertices of each of the three paths, and coalescing together the other end vertex of each of the three paths, the resulting graph is called the ϑ-graph, denoted by ϑ (b1, b2, b3). Let α(a, b1, b2, b3, s) be the graph obtained by merging one end of the path Ps with one vertex of a cycle Ca, and merging the other end of the path Ps with one vertex of ϑ(b1, b2, b3) of degree 3. If s = 1, denote β(a, b1, b2, b3) = α(a, b1, b2, b3, 1). In this paper, we give the necessity and sufficiency condition for the singularity of α(a, b1, b2, b3, s) and β(a, b1, b2, b3), and we also prove that the probability that any given α(a, b1, b2, b3, s) is a singular graph is equal to 35/64, the probability that any given β(a, b1, b2, b3) is a singular graph is equal to 9/16. From our main results we can conclude that such a &#945(a, b1, b2, b3, s) graph (&#946(a, b1, b2, b3) graph) is singular if 4|α or three bi(i = 1, 2, 3) are all odd numbers or exactly two of the three bi(i = 1, 2, 3) are odd numbers and the length of the cycle formed by the two odd paths in α(a, b1, b2, b3, s) graph (β(a, b1, b2, b3) graph) is a multiple of 4. The theoretical probability of these graphs being singular is more than half. [ABSTRACT FROM AUTHOR]

Given an n vertex graph whose edges have colored from one of τ colors C = {ci, C2,..., cr}, we define the Hamilton cycle color profile hcp(G) to be the set of vectors (mi, m2,..., mr) ∈ [0, n}r such that there exists a Hamilton cycle that is the concatenation of τ paths Pi, P2, ∙.., Pr, where Pi contains rΠι edges of color cι. We study hcp(Gn p) when the edges are randomly colored. We discuss the profile close to the threshold for the existence of a Hamilton cycle and the threshold for when ∕icp(Gnjf>) = {(mι, m2,..., mr) ∈ [0,n]r: mi + m2 + ∙ ∙ ∙ + mr = n}. [ABSTRACT FROM AUTHOR]

For a 2-connected graph G , the relative length of G , denoted by diff (G) , is the difference between the orders of a longest path and a longest cycle in G. This parameter is used as a measure to estimate how close a given graph is to a hamiltonian graph. Let σ k (G) be the least value of the sums of degrees of vertices in independent sets of cardinality k. In 2008, Paulusma and Yoshimoto proved that a 2-connected triangle-free graph G of order n with σ 4 (G) ≥ n + 2 satisfies diff (G) ≤ 1 unless G is isomorphic to one exceptional graph G 0. In this paper, we extend their result and prove that for an integer s with 2 3 (n + 4) < s ≤ n + 2 , a 2-connected triangle-free graph of order n with σ 4 (G) ≥ s satisfies diff (G) ≤ n + 3 − s unless s = σ 4 (G) = n + 2 and G = G 0. [ABSTRACT FROM AUTHOR]

For a family of graphs F , the Turán number e x (n , F) is the maximum number of edges in an n -vertex graph containing no member of F as a subgraph. The maximum number of edges in an n -vertex connected graph containing no member of F as a subgraph is denoted by e x c o n n (n , F). Katona and Xiao (2023) [7] posed the following conjecture: For a path P k on k vertices and a graph H with chromatic number more than 2, e x (n , { H , P k }) = n max ⁡ { ⌊ k 2 ⌋ − 1 , e x (k − 1 , H) k − 1 } + O k (1). In this paper we determine the exact value of e x c o n n (n , { P k , H }) for sufficiently large n. Moreover, we obtain asymptotical result for e x (n , { P k , H }) , which solves the conjecture proposed by Katona and Xiao. [ABSTRACT FROM AUTHOR]

Let K be any field, and let E be a finite graph with the property that every vertex in E is the base of at most one cycle (i.e., a graph with disjoint cycles). We explicitly construct the injective envelope of each simple left module over the Leavitt path algebra L K (E). The main idea girding our construction is that of a "formal power series" extension of modules, thereby developing for all graphs with disjoint cycles the understanding of injective envelopes of simple modules over L K (E) achieved previously for the simple modules over the Toeplitz algebra. [ABSTRACT FROM AUTHOR]

Given a graph G and an integer k, the k-Biclique problem asks whether G contains a complete bipartite subgraph with k vertices on each side. Whether there is an f(k) ċ |G|O(1)-time algorithm, solving k-Biclique for some computable function f has been a longstanding open problem. We show that k-Biclique is W[1]-hard, which implies that such an f(k) ċ |G|O(1)-time algorithm does not exist under the hypothesis W[1] ≠ FPT from parameterized complexity theory. To prove this result, we give a reduction which, for every n-vertex graph G and small integer k, constructs a bipartite graph H = (L&cupdot; R,E) in time polynomial in n such that if G contains a clique with k vertices, then there are k(k − 1)/2 vertices in L with nθ(1/k) common neighbors; otherwise, any k(k − 1)/2 vertices in L have at most (k+1)! common neighbors. An additional feature of this reduction is that it creates a gap on the right side of the biclique. Such a gap might have further applications in proving hardness of approximation results. Assuming a randomized version of Exponential Time Hypothesis, we establish an f(k) ċ |G|o(&sqrt;k)-time lower bound for k-Biclique for any computable function f. Combining our result with the work of Bulatov and Marx [2014], we obtain a dichotomy classification of the parameterized complexity of cardinality constraint satisfaction problems. [ABSTRACT FROM AUTHOR]

Patnaik and Immerman introduced the dynamic complexity class DynFO of database queries that can be maintained by first-order dynamic programs with the help of auxiliary relations under insertions and deletions of edges. This article confirms their conjecture that the reachability query is in DynFO. As a byproduct, it is shown that the rank of a matrix with small values can be maintained in DynFO. It is further shown that the (size of the) maximum matching of a graph can be maintained in non-uniform DynFO, an extension of DynFO, with non-uniform initialisation of the auxiliary relations. [ABSTRACT FROM AUTHOR]

We say an algorithm on n × n matrices with integer entries in [−M,M] (or n-node graphs with edge weights from [−M,M]) is truly subcubic if it runs in O(n3 − Δ ċ poly(log M)) time for some Δ> 0. We define a notion of subcubic reducibility and show that many important problems on graphs and matrices solvable in O(n3) time are equivalent under subcubic reductions. Namely, the following weighted problems either all have truly subcubic algorithms, or none of them do: •The all-pairs shortest paths problem on weighted digraphs (APSP). •Detecting if a weighted graph has a triangle of negative total edge weight. •Listing up to n2.99 negative triangles in an edge-weighted graph. •Finding a minimum weight cycle in a graph of non-negative edge weights. •The replacement paths problem on weighted digraphs. •Finding the second shortest simple path between two nodes in a weighted digraph. •Checking whether a given matrix defines a metric. •Verifying the correctness of a matrix product over the (min, +)-semiring. •Finding a maximum subarray in a given matrix. Therefore, if APSP cannot be solved in n3−ε time for any ε> 0, then many other problems also need essentially cubic time. In fact, we show generic equivalences between matrix products over a large class of algebraic structures used in optimization, verifying a matrix product over the same structure, and corresponding triangle detection problems over the structure. These equivalences simplify prior work on subcubic algorithms for all-pairs path problems, since it now suffices to give appropriate subcubic triangle detection algorithms. Other consequences of our work are new combinatorial approaches to Boolean matrix multiplication over the (OR,AND)-semiring (abbreviated as BMM). We show that practical advances in triangle detection would imply practical BMM algorithms, among other results. Building on our techniques, we give two improved BMM algorithms: a derandomization of the combinatorial BMM algorithm of Bansal and Williams (FOCS’09), and an improved quantum algorithm for BMM. [ABSTRACT FROM AUTHOR]

The power graph P(G) of a finite group G is a graph whose vertex set is the group G and distinct elements x, y ∈ G are adjacent if one is a power of the other, that is, x and y are adjacent if x ∈ ⟨y⟩ or y ∈ ⟨x⟩. Suppose that G = P ×Q, where P (resp. Q) is a finite p-group (resp. q-group) of exponent p (resp. q) for distinct prime numbers p < q. In this paper, we determine necessary and sufficient conditions for existence of Hamiltonian cycles in P(G). [ABSTRACT FROM AUTHOR]

In this paper, we study the recently introduced scoring game played on graphs called the Edge-Balanced Index Game. This game is played on a graph by two players, Alice and Bob, who take turns colouring an uncoloured edge of the graph. Alice plays first and colours edges red, while Bob colours edges blue. The game ends once all the edges have been coloured. A player captures a vertex if more than half of its incident edges are coloured by that player, and the player that captures the most vertices wins. Using classical arguments from the field, we first prove general properties of this game. Namely, we prove that there is no graph in which Bob can win (if Alice plays optimally), while Alice can never capture more than 2 more vertices than Bob (if Bob plays optimally). Through dedicated arguments, we then investigate more specific properties of the game, and focus on its outcome when played in particular graph classes. Specifically, we determine the outcome of the game in paths, cycles, complete bipartite graphs, and Cartesian grids, and give partial results for trees and complete graphs. [ABSTRACT FROM AUTHOR]

A graph G is a common multiple of two graphs H1 and H2 if there exists a decomposition of G into edge-disjoint copies of H1 and also a decomposition of G into edge-disjoint copies of H2. If G is a common multiple of H1 and H2, and G has q edges, then we call G a (q;H1;H2) graph. Our paper deals with the following question: Given two graphs H1 and H2, for which values of q does there exist a (q;H1;H2) graph? when H1 is either a path or a star or a cycle and H2 is a complete bipartite graph. [ABSTRACT FROM AUTHOR]

Finding the optimal assignment of locomotives to fulfill freight train transportation schedule under time constraints is a complex problem, even on a linear section of the railway. In previous studies, a graph model was proposed that allows solving the assignment problem using a static graph algorithm. It was proved that finding the optimal assignment without constraints is equivalent to finding the minimal path cover of a specific acyclic graph. However, due to time constraints, the optimal solution may not be valid. This paper presents methods for modifying the found solution in order for it to satisfy the time constraints on locomotives. Two operations on path in the minimal path cover of a graph are introduced: crossover and changeover. They allow to rebuild the found solution without spoiling the admissible sequences of transportation, while the invalid ones are corrected. [ABSTRACT FROM AUTHOR]

The class of monitoring systems, which is equipped with mobile means of detection, is considered. Unmanned aerial vehicles are used as detection means. The area of responsibility of the system is a geographic space with counteraction for both detection equipment and objects of observation. An original approach to the development of a simulation model for detecting moving objects of observation in the area of a spatially distributed continuous monitoring system with a structure is proposed. The movement of sensors is displayed along trajectories, which are Hamiltonian cycles on the terrain graph. The new approach is to use the approach used to ensure the flexibility of the resulting solutions to the problem of monitoring space and the ability to respond quickly to various factors and other conditions of use based on self-organizing mechanisms. At the same time, both the system itself, designed to solve the tasks of continuous monitoring and the solutions found for specific monitoring tasks and spatially distributed systems, provide continuous monitoring and are resistant to destructive influences of various kinds. The constructed simulation model and the experiments performed using the principles of dynamic detection of detection means in the area of a spatially distributed continuous monitoring system. At each moment of time, the optimal configuration of the parameters is determined, which is used as the most effective solution of the problem from the point of time of detecting an object in the monitoring area of vision. The model does not depend on the type of sensors used in the network and the implementation of the ideological principles embodied in the concept of dynamic systems. Based on the results of the experiments carried out, conclusions are drawn about the characteristics of continuous monitoring, which provides a basis for further work to optimize these indicators. [ABSTRACT FROM AUTHOR]

This paper is concerned with calculating the Möbius index values and arrived results for a few standard graphs. Some standard graphs which we considered are Path graph, Cycle graph, Complete Graph, Star Graph, Shell graph, Wheel Graph, Gear graph, Helm Graph, the Web graph, Flower Graph. [ABSTRACT FROM AUTHOR]

Suspensions of hard core spherical particles of diameter D with inter-core connectivity range δ can be described in terms of random geometric graphs, where nodes represent the sphere centers and edges are assigned to any two particles separated by a distance smaller than δ. By exploiting the property that closed loops of connected spheres become increasingly rare as the connectivity range diminishes, we study continuum percolation of hard spheres by treating the network of connected particles as having a tree-like structure for small δ=D. We derive an analytic expression of the percolation threshold which becomes increasingly accurate as δ=D diminishes and whose validity can be extended to a broader range of connectivity distances by a simple rescaling. [ABSTRACT FROM AUTHOR]

Let F be a family of graphs. A graph is called F -free if it does not contain any member of F as a subgraph. The Turán number of F is the maximum number of edges in an n -vertex F -free graph and is denoted by ex (n , F). The same maximum under the additional condition that the graphs are connected is ex conn (n , F). Let P k be the path on k vertices, K m be the clique on m vertices. We determine ex (n , { P k , K m }) if k > 2 m − 1 and ex conn (n , { P k , K m }) if k > m for sufficiently large n. [ABSTRACT FROM AUTHOR]

An injective edge-coloring of graph G is an edge-coloring φ such that φ (e 1) ≠ φ (e 3) for any three consecutive edges e 1 , e 2 and e 3 of a path or a 3-cycle. Note that such an edge-coloring is not necessarily proper. The minimum number of colors required for an injective edge-coloring is called the injective chromatic index of G , denoted by χ i ′ (G). For every integer k ≥ 2 , we show that every k -degenerate graph G with maximum degree Δ satisfies χ i ′ (G) ≤ (4 k − 3) Δ − 2 k 2 − k + 3. We also prove that every graph G with Δ = 4 , it is injective 9-edge-colorable when its maximum average degree m a d (G) < 14 5 , injective 10-edge-colorable when m a d (G) < 3 , injective 11-edge-colorable when m a d (G) < 19 6 , and injective 12-edge-colorable when m a d (G) < 36 11 . [ABSTRACT FROM AUTHOR]

The secure domination numbers of the Cartesian products of two small graphs with paths or cycles is determined, as well as for Möbius ladder graphs. Prior to this work, in all cases where the secure domination number has been determined, the proof has either been trivial, or has been derived from lower bounds established by considering different forms of domination. However, the latter mode of proof is not applicable for most graphs, including those considered here. Hence, this work represents the first attempt to determine secure domination numbers via the properties of secure domination itself, and it is expected that these methods may be used to determine further results in the future. [ABSTRACT FROM AUTHOR]

A path-factor of a graph G is a spanning subgraph of G whose components are paths. A P≥d-factor of a graph G is a path-factor of G whose components are paths with at least d vertices, where d ≥ 2 is an integer. A graph G is called a P≥d-factor uniform graph if for any two different edges e1 and e2 of G, G admits a P≥d-factor containing e1 and avoiding e2. The binding number of G is defined by bind(G) = minn {NG(X)|/|X| : ∅ ≠ X ⊆ V(G),NG(X) ≠ V(G)}. In this paper, we prove that (i) a 3-connected graph G is a P≥2-factor uniform graph if bind(G) > 1; (ii) a 3-connected graph G is a P≥3-factor uniform graph if bind(G) > 10/7 . [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new kind of graph energy, the minimum edge covering energy, ECE(G). It depends both on the underlying graph G, and on its particular minimum edge covering CE. Upper and lower bounds for ECE(G) are established. The minimum edge covering energy and some of the coefficients of the polynomial of well-known families of graphs like Star, Path and Cycle Graphs are computed. [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]

We make progress on three long standing conjectures from the 1960s about path and cycle decompositions of graphs. Gallai conjectured that any connected graph on n vertices can be decomposed into at most ⌈n2⌉ paths, while a conjecture of Hajós states that any Eulerian graph on n vertices can be decomposed into at most ⌊n−12⌋ cycles. The Erdős–Gallai conjecture states that any graph on n vertices can be decomposed into O(n) cycles and edges. We show that if G is a sufficiently large graph on n vertices with linear minimum degree, then the following hold. (i)G can be decomposed into at most n2+o(n) paths.(ii)If G is Eulerian, then it can be decomposed into at most n2+o(n) cycles.(iii)G can be decomposed into at most 3n2+o(n) cycles and edges.If in addition G satisfies a weak expansion property, we asymptotically determine the required number of paths/cycles for each such G. (iv)G can be decomposed into max{odd(G)2,Δ(G)2}+o(n) paths, where odd(G) is the number of odd‐degree vertices of G.(v)If G is Eulerian, then it can be decomposed into Δ(G)2+o(n) cycles.All bounds in (i)–(v) are asymptotically best possible. [ABSTRACT FROM AUTHOR]

We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time 2O(p k)(n+m). Under the Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphs cannot be solved in time 2o(p k)(n + m)O(1) [de Berg et al., STOC 2018], hence our algorithm is optimal. Besides the 2O(p k)(n + m)O(1)-time algorithm for the (arguably) much simpler Vertex Cover problem by de Berg et al. [STOC 2018] (which easily follows from the existence of a 2k-vertex kernel for the problem), this is the only known ETH-optimal fixed-parameter tractable algorithm on UDGs. Previously, Long Path and Long Cycle on unit disk graphs were only known to be solvable in time 2O(p k log k)(n + m). This algorithm involved the introduction of a new type of a tree decomposition, entailing the design of a very tedious dynamic programming procedure. Our algorithm is substantially simpler: we completely avoid the use of this new type of tree decomposition. Instead, we use a marking procedure to reduce the problem to (a weighted version of) itself on a standard tree decomposition of width O(p k). [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]

A (p,q) - graph G is said to have (1;N) - Arithmetic labelling if there is a one-one function from the vertex set V (G) to f0; 1;N; (N + 1); 2N; (2N + 1); :::; (q 1)N; (q 1) (N + 1)g so that the values of the edges, obtained as the sums of the labelling assigned to their end vertices can be arranged in the arithmetic progression 1; (N + 1); (2N + 1); :::; (q 1)N +1: In this paper we prove that certain chain of even cycles, splitting graph of paths and splitting graph of cycles C4m have (1,N) - Arithmetic Labelling for every positive integer N > 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]

The connectivity of a graph G , κ (G) , is the minimum cardinality over all vertex-cuts in G , and the value of κ (G) can be determined using Menger's theorem. It has long been one of the most important factors that characterize both graph reliability and fault tolerability. A graph G is super connected if its minimum vertex-cut is always composed of a vertex's neighborhood. In this article we define the super H -connectivity κ ′ (G | H) and the super H ∗ -connectivity κ ′ (G | H ∗) as new measures to evaluate the connectedness of G , for which H denotes a connected graph that represents the structure of the clustered faults, and H ∗ denotes the union of the set of all connected subgraphs of H and the set of the trivial graph. Then we establish both κ ′ (Q n | H) and κ ′ (Q n | H ∗) for H ∈ { K 1 , m ∣ m = 1 , 2 , 3 , 4 } ∪ { P 4 , C 4 } , where Q n denotes the n -dimensional hypercube, K 1 , m denotes the m -star structure for m ≥ 1 , P 4 denotes a path of order four and C 4 is a cycle of order four. [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]

Let H be a graph and p be an integer. The edge blow-up H p of H is the graph obtained from replacing each edge in H by a copy of K p where the new vertices of the cliques are all distinct. Let C k and P k denote the cycle and path with k vertices, respectively. In this paper, we find sharp upper bounds for ex (n , K 3 , C 3 3) and the exact value for ex (n , K 3 , P 4 3). Moreover, we determine the graphs attaining these bounds. [ABSTRACT FROM AUTHOR]

For an undirected graph or multigraph G = (V, E) and a function f : V → ℤ+, an f-factor is a subgraph whose degree function is f. For integral edge weights of maximum magnitude W our algorithm finds a maximum weight f-factor in time Õ(Wf(V)ω), where f(V ) = ∑v∈V f(v) and ω is the exponent of matrix multiplication. The algorithm is randomized and has two versions. For worst-case time the algorithm is correct with high probability. For expected time the algorithm is Las Vegas. The algorithm is based on a detailed analysis of the structure of the optimum blossoms. A special case gives a representation for single-source shortest-paths in conservative undirected graphs, generalizing the standard shortest-path tree to a "tree of cycles". The representation can be constructed by a randomized algorithm with the same time bound as above, or deterministically by an algorithm for maximum weight matching, achieving time O(n(m+n log n)) or O(√n mlog (nW)). [ABSTRACT FROM AUTHOR]

Fix k ≥ 2 and let H be a graph with χ (H) = k + 1 containing a critical edge. We show that for sufficiently large n , the unique n -vertex H -free graph containing the maximum number of cycles is T k (n). This resolves both a question and a conjecture of Arman, Gunderson and Tsaturian [4]. [ABSTRACT FROM AUTHOR]