Search

The connected graph of degree sequence 3, 3, 3, 1, 1, 1 is called a net, and the vertices of degree 1 in a net are called its endvertices. Broersma conjectured in 1993 that a 2-connected graph G with no induced K 1 , 3 is hamiltonian if every endvertex of each induced net of G has degree at least (| V (G) | - 2) / 3 . In this paper we prove this conjecture in the affirmative. [ABSTRACT FROM AUTHOR]

Finding the exact integrality gap α for the LP relaxation of the metric travelling salesman problem (TSP) has been an open problem for over 30 years, with little progress made. It is known that 4 / 3 ≤ α ≤ 3 / 2 , and a famous conjecture states α = 4 / 3 . It has also been conjectured that the integrality gap is achieved for half-integer basic solutions of the linear program. For this problem, essentially two "fundamental" classes of instances have been proposed. This fundamental property means that in order to show that the integrality gap is at most ρ for all instances of the metric TSP, it is sufficient to show it only for the instances in the fundamental class. However, despite the importance and the simplicity of such classes, no apparent effort has been deployed for improving the integrality gap bounds for them. In this paper we take a natural first step in this endeavour, and consider the 1 / 2-integer points of one such class. We successfully improve the upper bound for the integrality gap from 3 / 2 to 10 / 7 for a superclass of these points for which a lower bound of 4 / 3 is proved. A key role in the proof of this result is played by finding Hamiltonian cycles whose existence is equivalent to Kotzig's result on "compatible Eulerian tours", and which lead us to delta-matroids for developing the related algorithms. Our arguments also involve other innovative tools from combinatorial optimization with the potential of a broader use. [ABSTRACT FROM AUTHOR]

Given a connected graph G = (V , E) . A subset C ⊆ V is a dominating set if every vertex of V is either in C or adjacent to a vertex in C. Further, C is a connected dominating set if C is a dominating set and the induced subgraph G[C] is connected. The Minimum Connected Dominating Set (Min-CDS) problem asks to find a connected dominating set with the minimum size, which finds applications in communication networks, in particular, as a virtual backbone in wireless sensor networks. This paper focuses on a variant of the classic Min-CDS problem, called Minimum Connected Dominating Set with Labeling (Min-CDSL), in which we are given a connected graph with vertex labels, and are required to find a connected dominating set C such that the number of labels in C (instead of |C|) is minimized. Min-CDSL is apparently a generalization of Min-CDS, and is undoubtedly NP - complete . We give an approximation algorithm for Min-CDSL within performance ratio bounded by ln | V (G) | + span (G) + 1 , where span (G) refers to the maximum span of the input labeled graph (i.e., the number of connected components of the induced subgraph by a single label). In general, span (G) ≪ | V (G) | and for a series of labeled graphs span (G) = O (1) . For a random graph G ∈ G n , p , span (G) = O (ln | V (G) |) almost surely, and thus our approximation ratio is O (ln | V (G) |) which is reasonable comparing with the best known approximation ratio ln | V (G) | + 1 for Min-CDS. [ABSTRACT FROM AUTHOR]

In this paper, we propose to study a wide class of combinatorial optimization problems called combinatorial optimization problems with labelling. First, we give a combinatorial method to deal with the labelling version of some classical combinatorial optimization problems including minimum vertex cover, maximum independent set, minimum dominating set and minimum set cover, and convert the labelling problems into the original problems by polynomial-time reduction. We show that, although the labelling version of these problem seems more universal than their original counterparts, they are actually equivalent to the corresponding original problem from an algorithmic point of view. Moreover, we generalize the greedy approach for solving submodular cover problem to its labelling version, and as simple applications of our new method, we use it to solve the labelling versions of the minimum weighted spanning tree and connected vertex cover problem in a unified way. [ABSTRACT FROM AUTHOR]

Given a graph property P, Bondy and Chvátal defined P to be k-stable if for any nonadjacent u , v ∈ V (G) , whenever G + u v has the property P and d (u) + d (v) ≥ k , then G itself has the property P. The smallest such k is called the stability ofP. We consider the graph parameters integrity, toughness, tenacity, and binding number. For each of these parameters, we provide the stability for the property that G has a value for that parameter which is at least c, for some fixed c. We also demonstrate how stability can lead to degree sequence theorems and compare these results to known degree sequence theorems that are best possible in a certain sense. [ABSTRACT FROM AUTHOR]

A graph G is strongly spanning trailable if for any e 1 = u 1 v 1 , e 2 = u 2 v 2 ∈ E (G) (possibly e 1 = e 2 ), G (e 1 , e 2) , which is obtained from G by replacing e 1 by a path u 1 v e 1 v 1 and by replacing e 2 by a path u 2 v e 2 v 2 , has a spanning (v e 1 , v e 2) -trail. A graph G is Hamilton-connected if there is a spanning path between any two vertices of V(G). In this paper, we first show that every 2-connected 3-edge-connected graph with circumference at most 8 is strongly spanning trailable with an exception of order 8. As applications, we prove that every 3-connected { K 1 , 3 , N 1 , 2 , 4 } -free graph is Hamilton-connected and every 3-connected { K 1 , 3 , P 10 } -free graph is Hamilton-connected with a well-defined exception. The last two results extend the results in Hu and Zhang (Graphs Comb 32: 685–705, 2016) and Bian et al. (Graphs Comb 30: 1099–1122, 2014) respectively. [ABSTRACT FROM AUTHOR]

Cancer is analyzed as an intelligent system of collaborating and computing cells. The limitations of the current regime of cancer research and treatment are addressed, and the resultant need for new paradigmatic thinking is presented. Features of intelligence pervade the natural world from humans to animals of all sizes and complexity to microorganisms. Yet, cancer has hitherto not been investigated as acting with intelligence as it evades the body's and the oncologist's failed attempts to eradicate it. In this analysis, concepts of computation, including self computation and the limits of computation; game playing; e-machine analysis; self-aware systems; P and NP-hard problems; and Boolean networks are addressed and related to features of cancer that can be described as intelligent. The implications of the developed theory of cancer's intelligence are discussed, together with several signposts and recommendations for new cancer research. [ABSTRACT FROM AUTHOR]

Although deep learning has recently increased in popularity, it suffers from various problems including high computational complexity, energy greedy computation, and lack of scalability, to mention a few. In this paper, we investigate an alternative brain-inspired method for data analysis that circumvents the deep learning drawbacks by taking the actual dynamical behavior of biological neural networks into account. For this purpose, we develop a general framework for dynamical systems that can evolve and model a variety of substrates that possess computational capacity. Therefore, dynamical systems can be exploited in the reservoir computing paradigm, i.e., an untrained recurrent nonlinear network with a trained linear readout layer. Moreover, our general framework, called EvoDynamic, is based on an optimized deep neural network library. Hence, generalization and performance can be balanced. The EvoDynamic framework contains three kinds of dynamical systems already implemented, namely cellular automata, random Boolean networks, and echo state networks. The evolution of such systems towards a dynamical behavior, called criticality, is investigated because systems with such behavior may be better suited to do useful computation. The implemented dynamical systems are stochastic and their evolution with genetic algorithm mutates their update rules or network initialization. The obtained results are promising and demonstrate that criticality is achieved. In addition to the presented results, our framework can also be utilized to evolve the dynamical systems connectivity, update and learning rules to improve the quality of the reservoir used for solving computational tasks and physical substrate modeling. [ABSTRACT FROM AUTHOR]

There have been researches on sufficient spectral conditions for Hamiltonian properties and path-coverable properties of graphs. Utilizing the Bondy–Chvátal closure, we provide a unified approach to study sufficient graph eigenvalue conditions for these properties and sharpen several former spectral Hamiltonian results on balanced bipartite graphs and complementary graphs. [ABSTRACT FROM AUTHOR]

Let |$G=(V(G), E(G))$| be a connected graph. A subset |$T \subseteq V(G)$| is called an |$R^{k}$| -vertex-cut, if |$G-T$| is disconnected and each vertex in |$V(G)-T$| has at least |$k$| neighbors in |$G-T$|⁠. The cardinality of a minimum |$R^{k}$| -vertex-cut is the |$R^{k}$| -vertex-connectivity of |$G$| and is denoted by |$\kappa ^{k}(G)$|⁠. |$R^{k}$| -vertex-connectivity is a new measure to study the fault tolerance of network structures beyond connectivity. In this paper, we study |$R^{1}$| -vertex-connectivity and |$R^{2}$| -vertex-connectivity of Cayley graphs generated by wheel graphs, which are denoted by |$AW_{n}$|⁠ , and show that |$\kappa ^{1}(AW_{n})=4n-7$| for |$n\geq 6$|⁠ ; |$\kappa ^{2}(AW_{n})=6n-12$| for |$n\geq 6$|⁠. [ABSTRACT FROM AUTHOR]

We propose new and original mathematical connections between Hamilton–Jacobi (HJ) partial differential equations (PDEs) with initial data and neural network architectures. Specifically, we prove that some classes of neural networks correspond to representation formulas of HJ PDE solutions whose Hamiltonians and initial data are obtained from the parameters of the neural networks. These results do not rely on universal approximation properties of neural networks; rather, our results show that some classes of neural network architectures naturally encode the physics contained in some HJ PDEs. Our results naturally yield efficient neural network-based methods for evaluating solutions of some HJ PDEs in high dimension without using grids or numerical approximations. We also present some numerical results for solving some inverse problems involving HJ PDEs using our proposed architectures. [ABSTRACT FROM AUTHOR]

In this paper, domination integrity of fuzzy graph and efficient fuzzy graph concepts is introduced with examples. An algorithm is developed to find whether an arc is strong or not. If it is strong, another algorithm will classify it as α strong arc and β strong arc. The next algorithm is used to find whether the given fuzzy graph is a fuzzy tree or not. Domination and integrity are two different parameters used to define the stability of a graph in various situations. Using the strong arc concept a new parameter, domination integrity is defined and lower and upper bounds are found. This paper discusses the domination integrity for standard graphs such as path, cycle and complete graph. The domination integrity for Cartesian product of fuzzy graphs is also discussed. Finally, the new class of fuzzy graph, efficient fuzzy graph, is introduced. Efficient fuzzy graph is a special type of fuzzy graph that has the same dominating set, other than vertex set V, for both fuzzy graph and its underlying crisp graph. [ABSTRACT FROM AUTHOR]

The k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a fixed integer k such that no two adjacent vertices are coloured alike. If each vertex u must be assigned a colour from a prescribed list L (u) ⊆ { 1 , ... , k } , then we obtain the List k-Colouring problem. A graph G is H-free if G does not contain H as an induced subgraph. We continue an extensive study into the complexity of these two problems for H-free graphs. The graph P r + P s is the disjoint union of the r-vertex path P r and the s-vertex path P s. We prove that List 3-Colouring is polynomial-time solvable for (P 2 + P 5) -free graphs and for (P 3 + P 4) -free graphs. Combining our results with known results yields complete complexity classifications of 3-Colouring and List 3-Colouring on H-free graphs for all graphs H up to seven vertices. [ABSTRACT FROM AUTHOR]

The fabrication of nanomaterials from the top-down gives precise structures but it is costly, whereas bottom-up assembly methods are found by trial and error. Nature evolves materials discovery by refining and transmitting the blueprints using DNA mutations autonomously. Genetically inspired optimisation has been used in a range of applications, from catalysis to light emitting materials, but these are not autonomous, and do not use physical mutations. Here we present an autonomously driven materials-evolution robotic platform that can reliably optimise the conditions to produce gold-nanoparticles over many cycles, discovering new synthetic conditions for known nanoparticle shapes using the opto-electronic properties as a driver. Not only can we reliably discover a method, encoded digitally to synthesise these materials, we can seed in materials from preceding generations to engineer more sophisticated architectures. Over three independent cycles of evolution we show our autonomous system can produce spherical nanoparticles, rods, and finally octahedral nanoparticles by using our optimized rods as seeds. The ability to discover and optimise the synthesis of inorganic nanomaterials has significant impact on various fields, from sensing to medicine. Here, the authors use a genetic algorithm to drive a robotic platform toward a pre-defined, spectroscopic goal in order to discover and optimise the conditions for several nanoparticle shapes. [ABSTRACT FROM AUTHOR]

The minimum constraint removal (MCR) is one of the most important problems in motion planning and computational geometry. In this problem, there is no feasible path for a robot to move from the starting point towards the goal. Therefore, in order to find a collision-free path, the minimum constraints should be removed. The MCR problem is N P - h a r d when constraints have arbitrary shapes or are in shape of convex polygons. Since it is not possible to solve the problem by deterministic algorithms in an acceptable time for the problem with big data, scientists have tried to solve it by approximation methods. In this paper, we present a deterministic (not approximation) algorithm that solve the problem in a polynomial time. The simplification we used here is about the type of data (neither about the accuracy of the solution, nor about the size of data set). In this paper, a special case of this problem is presented, in which all the constraints are axis-aligned-unit squares and the obstacles have only local effects. Local effect means there are no two cells which have the same label sets. We propose an algorithm for this variant of the problem which can be used for big data. The proposed algorithm has O (n 3) time complexity in the worst case. [ABSTRACT FROM AUTHOR]

A graph G is called K 1 , 5 -free if G contains no K 1 , 5 as an induced subgraph. A tree with at most m leaves is called an m-ended tree. Let σ k (G) denote the minimum degree sum of k independent vertices in G. In this paper, it is shown that every connected K 1 , 5 -free graph G contains a spanning 5-ended tree if σ 6 (G) ≥ | G | - 1 . [ABSTRACT FROM AUTHOR]

Let T be a tree, a vertex of degree one is called a leaf. The set of leaves of T is denoted by Leaf (T) . The subtree T - Leaf (T) of T is called the stem of T and denoted by Stem (T) . In this paper, we give a sharp sufficient condition to show that a K 1 , t -free graph has a spanning tree whose stem has a few leaves. By applying the main result, we give improvements of previous related results. [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]

Let G be a graph and v ∈ V (G) . The neighbors of v, denoted by N(v), are the set of vertices adjacent to v. Let N [ v ] = N (v) ∪ { v } and J (u , v) = { w ∈ N (u) ∩ N (v) : N (w) ⊆ N [ u ] ∪ N [ v ] } . A graph G is called quasi-claw-free if J (u , v) ≠ ∅ for any u , v ∈ V (G) with d (u , v) = 2 . In this paper, we show that if G is a connected quasi-claw-free graph with σ k + 1 (G) ≥ | G | - k , then G contains a spanning k-ended tree, which generalizes some known results. [ABSTRACT FROM AUTHOR]

For two graphs A and B, a graph G is called { A , B } -free if G contains neither A nor B as an induced subgraph. Let P n denote the path of order n. For nonnegative integers k, ℓ and m, let N k , ℓ , m be the graph obtained from K 3 and three vertex-disjoint paths P k + 1 , P ℓ + 1 , P m + 1 by identifying each of the vertices of K 3 with one endvertex of one of the paths. Let Z k = N k , 0 , 0 and B k , ℓ = N k , ℓ , 0 . Bedrossian characterized all pairs { A , B } of connected graphs such that every 2-connected { A , B } -free graph is Hamiltonian. All pairs appearing in the characterization involve the claw ( K 1 , 3 ) and one of N 1 , 1 , 1 , P 6 and B 1 , 2 . In this paper, we characterize connected graphs that are (i) { K 1 , 3 , Z 2 } -free but not B 1 , 1 -free, (ii) { K 1 , 3 , B 1 , 1 } -free but not P 5 -free, or (iii) { K 1 , 3 , B 1 , 2 } -free but not P 6 -free. The third result is closely related to Bedrossian's characterization. Furthermore, we apply our characterizations to some forbidden pair problems. [ABSTRACT FROM AUTHOR]

In this paper we prove that every spanning tree of a 3-connected 3-regular graph, except for K 4 and K 2 □ K 3 , contains at least two contractible edges, and that every spanning tree of a minimally 3-connected graph, except for the wheel graphs, contains at least one contractible edge. Moreover, we show that every maximum matching of a 3-connected graph of order at least 6 that does not contain the maximal semiwheel graphs avoids at least four removable edges; every maximum matching of a 3-connected graph avoids at least two removable edges. [ABSTRACT FROM AUTHOR]

The Tutte poynomial T(G; x, y) of a graph G is a two-variable graph polynomial, and it gives interesting information about the graph. Many chemically interesting polycyclic polymers can be modeled by uniform or non-uniform polycyclic graphs. In this paper, we consider the Tutte poynomial of several classes of alternating polycyclic chains which contain phenylene chains and their dicyclobutadieno derivatives as special cases. Further, explicit closed formula of the number of spanning trees, the number of spanning forests and the number of spanning connected subgraphs of phenylenes (resp. the dicyclobutadieno derivatives of phenylenes) are obtained. [ABSTRACT FROM AUTHOR]

For an edge-coloured graph G , the minimum colour degree of G means the minimum number of colours on edges which are incident to each vertex of G. We prove that if G is an edge-coloured graph with minimum colour degree at least 5, then V (G) can be partitioned into two parts such that each part induces a subgraph with minimum colour degree at least 2. We show this theorem by proving amuch stronger form. Moreover, we point out an important relationship between our theorem and Bermond and Thomassen's conjecture in digraphs. [ABSTRACT FROM AUTHOR]

Modern computers allow a methodical search of possibly billions of experiments and the exploitation of interactions that are not known in advance. This enables a bottom-up process of design by assembling or configuring systems and testing the degree to which they fulfill the desired goal. We give two detailed examples of this process. One is referred to as Cartesian genetic programming and the other evolution-in-materio. In the former, evolutionary algorithms are used to exploit the interactions of software components representing mathematical, logical, or computational elements. In the latter, evolutionary algorithms are used to manipulate physical systems particularly at the electrical or electronic level. We compare and contrast both approaches and discuss possible new research directions by borrowing ideas from one and using them in the other. [ABSTRACT FROM AUTHOR]

The reservoir computing (RC) framework states that any nonlinear, input-driven dynamical system (the reservoir) exhibiting properties such as a fading memory and input separability can be trained to perform computational tasks. This broad inclusion of systems has led to many new physical substrates for RC. Properties essential for reservoirs to compute are tuned through reconfiguration of the substrate, such as change in virtual topology or physical morphology. As a result, each substrate possesses a unique 'quality'-obtained through reconfiguration- to realize different reservoirs for different tasks. Here we describe an experimental framework to characterize the quality of potentially any substrate for RC. Our framework reveals that a definition of quality is not only useful to compare substrates, but can help map the non-trivial relationship between properties and task performance. In the wider context, the framework offers a greater understanding as to what makes a dynamical system compute, helping improve the design of future substrates for RC. [ABSTRACT FROM AUTHOR]

The scattering number and isolated scattering number of a graph have been introduced in relation to Hamiltonian properties and network vulnerability, and the isolated scattering number plays an important role in characterizing graphs with a fractional 1-factor. Here we investigate the computational complexity of one variant, namely, the weighted isolated scattering number. We give a polynomial time algorithm to compute this parameter of interval graphs, an important subclass of perfect graphs. [ABSTRACT FROM AUTHOR]

The computational complexity of the Vertex Coloring problem is known for all hereditary classes of graphs defined by forbidding two connected five-vertex induced subgraphs, except for seven cases. We prove the polynomial-time solvability of four of these problems: for (P5, dart)-free graphs, (P5, banner)-free graphs, (P5, bull)-free graphs, and (fork, bull)-free graphs. [ABSTRACT FROM AUTHOR]

The clique‐based structure of chordal graphs allows the development of efficient solutions for many algorithmic problems. In this context, the minimal vertex separators play a decisive role. In this paper, we study properties of these structures, presenting a linear time determination of the toughness of strictly chordal graphs. We prove that every 1‐tough strictly chordal graph is Hamiltonian. This result leads to the characterization of a new class, the Hamiltonian strictly chordal graphs. We also prove that graphs belonging to this class are cycle extendable. [ABSTRACT FROM AUTHOR]

A leaf of a tree is a vertex of degree one and a branch vertex of a tree is a vertex of degree strictly greater than two. This paper shows two degree conditions for graphs to have spanning trees with total bounded number of branch vertices and leaves. Moreover, the sharpness of our results is shown. [ABSTRACT FROM AUTHOR]

Copyright of Saber: Revista Multidisciplinaria del Consejo de Investigacion is the property of Universidad de Oriente and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Logical gates are constructed based on a method of numerical modeling of natural erosion of sandstone. Values of logical variables are determined by the presence of sandstone. The presence of sandstone corresponds to the logical value of True, whereas the absence of material corresponds to the False value. Logical functions are computed through the formation of sandstone structures at action of natural erosion where loading conditions are specified. AND and XOR gates and a one-bit binary half-adder are implemented. [ABSTRACT FROM AUTHOR]

A linear ordering of the vertices of a graph Gseparates two edges of G if both the endpoints of one precede both the endpoints of the other in the order. We call two edges {a,b} and {c,d} of Gstrongly independent if the set of endpoints {a,b,c,d} induces a 2K2 in G. The induced separation dimension of a graph G is the smallest cardinality of a family L of linear orders of V(G) such that every pair of strongly independent edges in G are separated in at least one of the linear orders in L. For each k∈N, the family of graphs with induced separation dimension at most k is denoted by ISD(k). In this article, we initiate a study of this new dimensional parameter. The class ISD(1) or, equivalently, the family of graphs which can be embedded on a line so that every pair of strongly independent edges are disjoint line segments, is already an interesting case. On the positive side, we give characterizations for chordal graphs in ISD(1) which immediately lead to a polynomial time algorithm which determines the induced separation dimension of chordal graphs. On the negative side, we show that the recognition problem for ISD(1) is NP-complete for general graphs. Nevertheless, we show that the maximum induced matching problem can be solved efficiently in ISD(1). We then briefly study ISD(2) and show that it contains many important graph classes like outerplanar graphs, chordal graphs, circular arc graphs and polygon-circle graphs. Finally, we describe two techniques to construct graphs with large induced separation dimension. The first one is used to show that the maximum induced separation dimension of a graph on n vertices is Θ(lgn) and the second one is used to construct AT-free graphs with arbitrarily large induced separation dimension. The second construction is also used to show that, for every k≥2, the recognition problem for ISD(k) is NP-complete even on AT-free graphs. [ABSTRACT FROM AUTHOR]

This paper examines a schema for graph-theoretic clustering using node-based resilience measures. Node-based resilience measures optimize an objective based on a critical set of nodes whose removal causes some severity of disconnection in the network. Beyond presenting a general framework for the usage of node based resilience measures for variations of clustering problems, we experimentally validate the usefulness of such methods in accomplishing the following: (i) clustering a graph in one step without knowing the number of clusters a priori; (ii) removing noise from noisy data; and (iii) detecting overlapping communities. We demonstrate that this clustering schema can be applied successfully using a wide range of data, including both real and synthetic networks, both natively in graph form and also expressed as point sets. [ABSTRACT FROM AUTHOR]

Because of its application in the field of security in wireless sensor networks, k-path vertex cover (VCPk) has received a lot of attention in recent years. Given a graph G=(V,E), a vertex set C⊆V is a k-path vertex cover (VCPk) of G if every path on k vertices has at least one vertex in C, and C is a connected k-path vertex cover of G (CVCPk) if furthermore the subgraph of G induced by C is connected. A homogeneous wireless sensor network can be modeled as a unit disk graph. This paper presents a new PTAS for MinCVCPk on unit disk graphs. Compared with previous PTAS given by Liu et al., our method not only simplifies the algorithm and reduces the time-complexity, but also simplifies the analysis by a large amount. [ABSTRACT FROM AUTHOR]

Las Vergnas (CR Acad Sci Paris Sér A 272:1297-1300, 1971), and Broersma and Tuinstra (J Graph Theory 29:227-237, 1998) independently investigated a degree sum condition for a graph to have a spanning tree whose number of leaves is restricted. In this paper, we obtain the bipartite analogy of this result. [ABSTRACT FROM AUTHOR]

A partition of the vertex set V(G) of a graph G into V(G) = V1∪V2∪· · ·∪ Vk is called a k-strong subcoloring if d(x, y) = 2 in G for every x, y ∈ Vi, 1 ≤ i ≤ k where d(x, y) denotes the length of a shortest x-y path in G. The strong subchromatic number is defined as χsc(G) = min{k: G admits a k-strong subcoloring}. In this paper, we explore the complexity status of the STRONGSUBCOLORING problem: for a given graph G and a positive integer k, STRONGSUBCOLORING is to decide whether G admits a k-strong subcoloring. We prove that STRONGSUBCOLORING is NP-complete for subcubic bipartite graphs and the problem is polynomial time solvable for trees. In addition, we prove the following dichotomy results: (i) for the class of K1,r-free split graphs, STRONGSUBCOLORING is in P when r ≤ 3 and NP-complete when r > 3 and (ii) for the class of H-free graphs, STRONGSUBCOLORING is polynomial time solvable only if H is an induced subgraph of P4; otherwise the problem is NP-complete. Next, we consider a lower bound on the strong subchromatic number. A strong set is a set S of vertices of a graph G such that for every x, y ∈ S, d(x, y) = 2 in G and the cardinality of a maximum strong set in G is denoted by αs (G). Clearly, αs (G) ≤ χsc(G). We consider the complexity status of the StrongSet problem: given a graph G and a positive integer k, StrongSet asks whether G contains a strong set of cardinality k. We prove that StrongSet is NP-complete for (i) bipartite graphs and (ii) K1,4-free split graphs, and it is polynomial time solvable for (i) trees and (ii) P4-free graphs. [ABSTRACT FROM AUTHOR]

A problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well as handle any vertex recoloring requests. Our main concern is the greedy approach and characterization of graph classes for which it is possible to decide in polynomial time whether for the fixed forbidden graph F and positive integer k the greedy algorithm ever uses more than k colors in dynamic F-free coloring. For various classes of graphs we give such characterizations in terms of a finite number of minimal forbidden graphs thus solving the above-mentioned problem for the so-called F-trees when F is 2-connected, and for classical trees, when F is a path of order 3 (the latter variant is also known as subcoloring or 1-improper coloring). [ABSTRACT FROM AUTHOR]

Given a graph G=(V,E,L) and a coloring function ℓ:E→L, that assigns a color to each edge of G from a finite color set L, the rainbow spanning forest problem (RSFP) consists of finding a rainbow spanning forest of G such that the number of components is minimum. A spanning forest is rainbow if all its components (trees) are rainbow. A component whose edges have all different colors is called rainbow component. The RSFP on general graphs is known to be NP-complete. In this paper we use the 3-SAT Problem to prove that the RSFP is NP-complete on trees and we prove that the problem is solvable in polynomial time on paths, cycles and if the optimal solution value is equal to 1. Moreover, we provide an approximation algorithm for the RSFP on trees and we show that it approximates the optimal solution within 2. [ABSTRACT FROM AUTHOR]

In this paper, we survey results and conjectures on degree conditions for the existence of vertex-disjoint cycles and paths. In particular, we focus on the type of degree conditions, the type of cycles or paths, and relations between results or conjectures. [ABSTRACT FROM AUTHOR]

Given a graph $$G=(V,E)$$ with a label set $$L = \{\ell _1, \ell _2, \ldots , \ell _q \}$$ , in which each edge has a label from L, and a source $$s \in V$$ together with a sink $$t \in V$$ , the Minimum Label s- t Cut problem asks to pick a set $$L' \subseteq L$$ of labels with minimized cardinality, such that the removal of all edges with labels in $$L'$$ from G disconnects s and t. Let $$n = |V|$$ and $$m = |E|$$ . The previous best known approximation ratio for this problem in literature is $$O(m^{1/2})$$ . We present two simple and purely combinatorial approximation algorithms for the problem with ratios $$O(n^{2/3}/\text {OPT}^{1/3})$$ and $$O(m^{1/2} / \text {OPT}^{1/2})$$ , where $$\text {OPT}$$ is the optimal value of the input instance. The former result gives the first approximation ratio which is sublinear in n for the problem, and in particular applies to the instances with dense graphs (e.g., $$m = \varTheta (n^2)$$ ). The latter result improves the previous ratio $$O(m^{1/2})$$ , as we can always assume that $$\text {OPT}$$ is a super-constant. [ABSTRACT FROM AUTHOR]

Let G be a simple 2-connected, $$C_4$$ -free graph with minimum degree $$\delta (G)\ge 4$$ and leaf number L( G) such that $$\delta (G)\ge \displaystyle \frac{1}{2}L(G)$$ . We show that G is Hamiltonian. In addition, we provide family of graphs to show that the results are best possible for aforementioned class of graphs. The results, apart from supporting the conjecture (Graffiti.pc 190) of the computer program Graffiti.pc, instructed by DeLaVi $${\tilde{n}}$$ a, provide a new sufficient condition for Hamiltonicity in $$C_4$$ -free graphs. [ABSTRACT FROM AUTHOR]

A vertex coloring is said to be 2-distance if any two distinct vertices of distance at most 2 receive different colors. Let G be a planar graph with girth at least 5. In this paper, we prove that G admits a 2-distance coloring with at most Δ (G) +3 colors if Δ (G) ≥ 339. [ABSTRACT FROM AUTHOR]

The dimension of a graph G is defined to be the minimum n such that G has a representation as a unit-distance graph in $${{\mathbb {R}}}^n$$ . In this article, we show that a dimension 6 graph with minimum edge-set has exactly 21 edges, with this minimum realized only in the case of the complete graph $$K_7$$ . This result answers a higher-dimensional analogue of a question posed by Paul Erdős and presented by Alexander Soifer in The Mathematical Coloring Book. [ABSTRACT FROM AUTHOR]

As a part of a heuristic for the fast detection of new word combinations in text streams, we consider the NP-hard Partial Set Cover of Pairs problem. There we wish to cover a maximum number of pairs of elements by a prescribed number of sets from a given set family. While the approximation ratio of the greedy algorithm for the classic Partial Set Cover problem is completely understood, the same question for covering of pairs is intrinsically more complicated, since the pairs insert some graph-theoretic structure. The best approximation guarantee for the first greedy step can be rephrased as a problem in extremal combinatorics: Assume that we may place a fixed number of subsets of fixed and equal size in a set, how many different pairs of elements can we cover? In this paper we introduce a method to calculate optimal approximation guarantees, and we demonstrate its use on the smallest set families. [ABSTRACT FROM AUTHOR]

A graph is called $$2K_2$$ -free if it does not contain two independent edges as an induced subgraph. Gao and Pasechnik conjectured that every $$\frac{3}{2}$$ -tough $$2K_2$$ -free graph with at least three vertices has a spanning trail with maximum degree at most 4. In this paper, we confirm this conjecture. We also provide examples for all $$t < \frac{5}{4}$$ of t-tough graphs that do not have a spanning trail with maximum degree at most 4. [ABSTRACT FROM AUTHOR]