Search

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, 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]

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]

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]

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]

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]

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]

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]

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]

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]

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

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]

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]

For any finite simple undirected graph G = (V (G) , E (G)) , we consider the binary relation ← G on the powerset 𝒫 (V (G)) of its vertex set given by B ← G A if ⋂ v ∈ B N G (v) ⊇ ⋂ v ∈ A N G (v) , where N G (v) denotes the neighborhood of a vertex v. We call the above relation set adiacence dependency (sa)-dependency of G. With the relation ← G we associate an intersection-closed family C L s a (G) of vertex subsets and the corresponding induced lattice ℭ (G) : = (C L s a (G) , ⊆) , which we call sa-lattice of G. Through the equality of sa-lattices, we introduce an equivalence relation ≡ s a between graphs and propose three different classifications of graphs based on such a relation. Furthermore, we determine the sa-lattice for various graph families, such as complete graphs, complete bipartite graphs, cycles and paths and, next, we study such a lattice in relation to the Cartesian and the tensor product of graphs, verifying that in most cases it is a graded lattice. Finally, we provide two algorithms, namely, the T-DI ALGORITHM and the O-F ALGORITHM, in order to provide two different computational ways to construct the sa-lattice of a graph. For the O-F ALGORITHM we also determine its computational complexity. [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]

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]

An interconnection network is a complex connection of a set of processors and communication links between different processors which is utilized to exchange data between processors in the parallel computing system. Graph embedding is a vital tool used to run parallel algorithms in computer networks in which placing different modules on the board is one of the main cost criteria. By finding the optimal layout, the placement problem in circuit designs which does not have any deterministic algorithms can be solved. The complete multipartite graph is a widely used network topology with a high degree of reliability due to its flexible choice of network size. Recently a study was made by computing the optimal layout of balanced complete multipartite graphs into host graphs taken from the Cartesian product of elements in the set {path, cycle}, but leaving the case of product of paths as an open problem. This paper aims to solve such an open problem and the key idea is to locate suitable optimal sets in balanced complete multipartite graphs with respect to maximizing the number of edges in the located sets. Besides, we compute the layout in the case of host graphs like k -rooted complete binary trees, k -rooted sibling trees and the Cartesian product of path P 2 and complete binary trees. [ABSTRACT FROM AUTHOR]

For a 2-connected graph G on n vertices and two vertices x , y ∈ V (G) , we prove that there is an (x , y) -path of length at least k , if there are at least n − 1 2 vertices in V (G) \ { x , y } of degree at least k. This strengthens a celebrated theorem due to Erdős and Gallai in 1959. As the first application of this result, we show that a 2-connected graph with n vertices contains a cycle of length at least 2 k , if it has at least n 2 + k vertices of degree at least k. This confirms a 1975 conjecture made by Woodall. As other applications, we obtain some results which generalize previous theorems of Dirac, Erdős-Gallai, Bondy, and Fujisawa et al., present short proofs of the path case of Loebl-Komlós-Sós Conjecture which was verified by Bazgan et al. and a conjecture of Bondy on longest cycles (for large graphs) which was confirmed by Fraisse and Fournier, and make progress on a conjecture of Bermond. [ABSTRACT FROM AUTHOR]

Let G be a simple, connected, triangle-free graph with minimum degree δ and leaf number L(G). We prove that if L(G) ≤2δ − 1, then G is either Hamiltonian or G ∈ ℱ2, where ℱ2 is the class of non-Hamiltonian graphs with leaf number 2δ − 1. Further, if L(G) ≤ 2δ, we show that G is traceable or G ∈ ℱ3. The results, apart from strengthening theorems in [17, 16] for this class of graphs, provide a sufficient condition for a triangle-free graph to be Hamiltonian or traceable based on leaf number and minimum degree. [ABSTRACT FROM AUTHOR]

A chordless cycle, or equivalently a hole, in a graph G is an induced subgraph of G which is a cycle of length at least 4. We prove that the Erdős-Pósa property holds for chordless cycles, which resolves the major open question concerning the Erdős-Pósa property. Our proof for chordless cycles is constructive: in polynomial time, one can find either k + 1 vertex-disjoint chordless cycles, or c 1 k 2 log ⁡ k + c 2 vertices hitting every chordless cycle for some constants c 1 and c 2. It immediately implies an approximation algorithm of factor O (opt log ⁡ opt) for Chordal Vertex Deletion. We complement our main result by showing that chordless cycles of length at least ℓ for any fixed ℓ ≥ 5 do not have the Erdős-Pósa property. [ABSTRACT FROM AUTHOR]

We study the problem of online graph exploration on undirected graphs, where a searcher has to visit every vertex and return to the origin. Once a new vertex is visited, the searcher learns of all neighboring vertices and the connecting edge weights. The goal of such an exploration is to minimize its total cost, where each edge traversal incurs a cost of the corresponding edge weight. We investigate the problem on tadpole graphs (also known as dragons, kites), which consist of a cycle with an attached path. The construction by Miyazaki et al. (The online graph exploration problem on restricted graphs, IEICE Transactions 92-D (9), 2009) can be extended to show that every online algorithm on these graphs must have a competitive ratio of 2 − ε , but the authors did not investigate non-unit edge weights. We show via amortized analysis that a greedy approach yields a matching competitive ratio of 2 on tadpole graphs, for arbitrary non-negative edge weights. Moreover, we also briefly discuss the topic of advice complexity on cycle and tadpole graphs. [ABSTRACT FROM AUTHOR]

• A (k − 1)-approximation for the minimum weight connected- k -subgraph cover for a graph with girth > 2 k / 3 when k > 4. • This improves a previous result by relaxing the girth constraint from at least k to greater than 2 k / 3. • It improves previous ratio O (log ⁡ k) for the cardinality version when k < 45. For a given graph G , the minimum weight connected- k -subgraph cover problem (MinWC k SC) is to find a minimum weight vertex subset C of G such that each connected subgraph of G on k vertices contains at least one vertex of C. Previously, Zhang et al. [37] presented a (k − 1) -approximation algorithm for MinWC k SC under the assumption that the girth of G , which is the length of a shortest cycle of G , is at least k. In this paper, we improve this result by showing that (k − 1) -approximation can be achieved when the girth requirement is relaxed from k to 2 k / 3. [ABSTRACT FROM AUTHOR]

In a zero forcing process , an initial vertex coloring of a graph is updated iteratively according to the following conversion rule: an uncolored vertex becomes colored if it is the only uncolored neighbor of some colored vertex. In this process, a zero forcing set is an initial set of colored vertices such that all the remaining vertices will ultimately change from uncolored to colored, and the zero forcing number is the minimum cardinality of a zero forcing set. We investigate two related concepts: a zero blocking set is the complement of a set which is not a zero forcing set, and the zero blocking number is the minimum cardinality of a zero blocking set. We provide a tight upper bound for the zero blocking number of Cartesian products of two arbitrary graphs. Exact values that are smaller than this general upper bound are also established when one of the graphs in the product is a cycle and the other is a path with at least as many vertices as the cycle. [ABSTRACT FROM AUTHOR]

In this paper we study the Grundy domination number on the X -join product G ↩ R of a graph G and a family of graphs R = { G v : v ∈ V (G) }. The results led us to extend the few known families of graphs where this parameter can be efficiently computed. We prove that if, for all v ∈ V (G) , the Grundy domination number of G v is given, and G is a power of a cycle, a power of a path, or a split graph, computing the Grundy domination number of G ↩ R can be done in polynomial time. In particular, our results for powers of cycles and paths are derived from a polynomial reduction to the Maximum Weight Independent Set problem on these graphs. As a consequence, we derive closed formulas to compute the Grundy domination number of the lexicographic product G ∘ H when G is a power of a cycle, a power of a path or a split graph, generalizing the results on cycles and paths given by Brešar et al. in 2016. Moreover, our results on the X -join product when G is a split graph also provide polynomial-time algorithms to compute the Grundy domination number for (q , q − 4) graphs, partner limited graphs and extended P 4 -laden graphs, graph classes that are high in the hierarchy of few P 4 's graphs. [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]

A graphical model provides a compact and efficient representation of the association structure in a multivariate distribution by means of a graph. Relevant features of the distribution are represented by vertices, edges and higher-order graphical structures such as cliques or paths. Typically, paths play a central role in these models because they determine the dependence relationships between variables. However, while a theory of path coefficients is available for directed graph models, little research exists on the strength of the association represented by a path in an undirected graph. Essentially, it has been shown that the covariance between two variables can be decomposed into a sum of weights associated with each of the paths connecting the two variables in the corresponding concentration graph. In this context, we consider concentration graph models and provide an extensive analysis of the properties of path weights and their interpretation. Specifically, we give an interpretation of covariance weights through their factorization into a partial covariance and an inflation factor. We then extend the covariance decomposition over the paths of an undirected graph to other measures of association, such as the marginal correlation coefficient and a quantity that we call the inflated correlation. Application of these results is illustrated with an analysis of dietary intake networks. [ABSTRACT FROM AUTHOR]

Let G be a connected simple graph. A graph H is said to be a m-Super subdivision of G, if every edge of G is replaced by the complete bipartite graph Km,m with m > 2 in such a way that the end vertices of the edge are merged with any two vertices of the same partite set A or B of Km,m after removal of the edge of G. In this paper, we prove that m-Super subdivision of path and cycle are graceful. [ABSTRACT FROM AUTHOR]

Consider a game played on the edge set of the infinite clique by two players, Builder and Painter. In each round, Builder chooses an edge and Painter colors it red or blue. Builder wins by creating either a red copy of G or a blue copy of H for some fixed graphs G and H. The minimum number of rounds within which Builder can win, assuming both players play perfectly, is the on-line Ramsey number r ̃ (G , H). In this paper, we prove some new general lower and upper bounds for on-line Ramsey numbers r ̃ (C 3 , P k) and r ̃ (C 4 , P k). [ABSTRACT FROM AUTHOR]

A graph U is an induced universal graph for a family F of graphs if every graph in F is a vertex-induced subgraph of U. Recently, for the family of all undirected graphs on n vertices, Alon [Geom. Funct. Anal. 2017] [3] proved the existence of an induced universal graph with (1 + o (1)) ⋅ 2 (n − 1) ∕ 2 vertices improving the previous best bound of 16 ⋅ 2 n ∕ 2 by Alstrup et al. (2015) and matching the lower bound of 2 (n − 1) ∕ 2 by Moon (1965) up to lower order additive terms. We continue this line of research of finding the size of the smallest induced universal graph up to lower order additive terms for some basic graph families. For the family of graphs with n vertices and bounded degree D = O (1) , Alon and Nenadov [Math. Proc. Camb. Philos. Soc. 2017] [4] showed that the smallest induced universal graph has size Θ n D ∕ 2 , but it remains to find the constant hidden in the O -notation. For even D the bound O n D ∕ 2 was already shown by Butler (2009). In order to find the correct constants for general D > 0 , it is natural first to consider the case D = 2. For D = 2 , Butler gave an induced universal graph of size 6. 5 n and subsequently, Esperet et al. (2008) found an induced universal graph for D = 2 of size 2. 5 n. We construct for D = 2 an even smaller induced universal graph with 2 n − 1 vertices. This proves a conjecture by Esperet et al. stating the existence of such a graph with 2 n + o (n) vertices. For the family of acyclic graphs on n vertices with maximum degree 2 we show that the smallest induced universal graph has size 3 n 2 . We also introduce the notion of size oblivious and size aware decoding, and relate this to families of induced universal graphs. For the family of graphs consisting of a single cycle we prove new upper and lower bounds on the complexity of size aware and size oblivious decoders. These new bounds separate the two notions. [ABSTRACT FROM AUTHOR]

A digraph is called oriented if there is at most one arc between two distinct vertices. An oriented graph $D$ is nonsingular if its adjacency matrix $A(D)$ is nonsingular. We characterise all nonsingular oriented graphs from three classes: graphs in which cycles are vertex disjoint, graphs in which all cycles share exactly one common vertex and graphs formed by cycles sharing a common path. As a straightforward corollary, the singularity of oriented bicyclic graphs is determined. [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]