Search

Existing graph-theoretic approaches to construct floor-plans for a given plane graph are mainly restricted to floor-plans with rectangular boundary. This paper introduces floor-plans with L -shaped boundary (boundary with only one concave corner). To ensure the L -shaped boundary, we introduce the concept of non-triviality of a floor-plan. A floor-plan with a rectilinear boundary with at least one concave corner is non-trivial if the number of concave corners can not be reduced without affecting the modules' adjacencies. Further, we present necessary and sufficient conditions for the existence of a non-trivial L -shaped floor-plan corresponding to a properly triangulated plane graph (PTPG) G. Also, we develop an O (n 3) algorithm for its construction, if it exists. • Construction of floorplans for a given graph is limited to rectangular boundaries. • We proposed the existence and construction of L-shaped floorplans. • Obtained L-shaped floorplans cannot be transformed into rectangular floorplans. [ABSTRACT FROM AUTHOR]

The traveling salesman problem (TSP) is one of the classic research topics in the field of operations research, graph theory and computer science. In this paper, we propose a generalized model of traveling salesman problem, denoted by generalized traveling salesman path problem. Let G = (V , E , c) be a weighted complete graph, in which c is a nonnegative metric cost function on edge set E , i.e., c : E → R +. The traveling salesman path problem aims to find a Hamiltonian path in G with minimum cost. Compared to the traveling salesman path problem, we are given extra vertex subset V ′ and edge subset E ′ in the problem proposed in this paper; its goal is to construct a path which traverses all the edges in E ′ while only needs to visit each vertex in V ′ exactly once. Based on integer programming, we give a mathematical model of the problem, and design a 1 + 5 2 -approximation algorithm for the problem by combining linear programming rounding strategy and a special graph structure. • In this paper, we consider a generalized model of traveling salesman problem. • Based on integer programming, we give a mathematical model of the problem. • Combining linear programming rounding strategy and a special graph structure, we propose a 1 + 5 2 -approximation algorithm. [ABSTRACT FROM AUTHOR]

The spanning trees of a graph constructed by the graph searches BFS and DFS are some of the most elementary structures in algorithmic graph theory. BFS-trees are first-in trees, i.e., every vertex is connected to its first visited neighbor. DFS-trees are last-in trees, i.e., every vertex is connected to its most recently visited neighbor. It is known since the 1980s that the problem of deciding whether a given spanning tree of a graph is a BFS-tree or a DFS-tree can be solved in linear time. Here, we will show that swapping the search-tree paradigms between these searches makes the problem hard, i.e., it is NP -complete to decide whether a spanning tree of a graph is a first-in-tree of a DFS or a last-in-tree of a BFS. To the best of our knowledge the latter result is the first hardness result for the recognition of last-in-trees for some graph search. Additionally, we study the complexity of both problems on split graphs. • Hardness of the recognition of last-in trees of BFS. • Hardness of the recognition of first-in trees of DFS. • Linear-time algorithm for the recognition of first-in trees of DFS on split graphs. • Better understanding of the last-in trees of generic search. [ABSTRACT FROM AUTHOR]

The chromatic number, which refers to the minimum number of colours required to colour the vertices of graphs properly, is one of the most central notions of the graph chromatic theory. Several of its aspects of interest have been investigated in the literature, including variants for modifications of proper colourings. These variants include, notably, the achromatic number of graphs, which is the maximum number of colours required to colour the vertices of graphs properly so that each possible combination of distinct colours is assigned along some edge. The behaviours of this parameter have led to many investigations of interest, bringing to light both similarities and discrepancies with the chromatic number. This work takes place in a recent trend aiming at extending the chromatic theory of graphs to the realm of signed graphs, and, in particular, at investigating how classic results adapt to the signed context. Most of the works done in that line to date are with respect to two main generalisations of proper colourings of signed graphs, attributed to Zaslavsky and Guenin. Generalising the achromatic number to signed graphs was initiated recently by Lajou, his investigations being related to Guenin's colourings. We here pursue this line of research, but with taking Zaslavsky's colourings as our notion of proper colourings. We study the general behaviour of our resulting variant of the achromatic number, mainly by investigating how known results on the classic achromatic number generalise to our context. Our results cover, notably, bounds, standard operations on graphs, and complexity aspects. [ABSTRACT FROM AUTHOR]

The main goal of this note is to provide a First-Order Logic with Betweenness (FOLB) axiomatization of the main classes of graphs occurring in Metric Graph Theory, in analogy to Tarski's axiomatization of Euclidean geometry. We provide such an axiomatization for weakly modular graphs and their principal subclasses (median and modular graphs, bridged graphs, Helly graphs, dual polar graphs, etc), basis graphs of matroids and even Δ-matroids, partial cubes and their subclasses (ample partial cubes, tope graphs of oriented matroids and complexes of oriented matroids, bipartite Pasch and Peano graphs, cellular and hypercellular partial cubes, almost-median graphs, netlike partial cubes), and Gromov hyperbolic graphs. On the other hand, we show that some classes of graphs (including chordal, planar, Eulerian, and dismantlable graphs), closely related with Metric Graph Theory, but defined in a combinatorial or topological way, do not allow such an axiomatization. [ABSTRACT FROM AUTHOR]

All spanning tree generation of a simple connected graph is a well-approached problem in graph theory. In this paper, an algorithm based on a new technique, namely divide-and-conquer, has been proposed. The performance of the proposed algorithm has also been benchmarked against several existing algorithms, including one algorithm implemented in parallel, in this domain. The basis of comparison is on the number of circuits generated and CPU time taken by each of the algorithms compared, using a set of randomly generated graph instances on a common platform. [ABSTRACT FROM AUTHOR]

A major breakthrough in the diagnosis of t -diagnosable systems occurred when Dahbura and Mason developed a diagnosis algorithm under the PMC model using the matching theory in bipartite graphs. In this paper we introduce a new testing model called the symmetric PMC(SPMC) model. Our main contributions are as follows: We prove that the diagnosability of an n -dimensional hypercube under the SPMC model is almost twice its diagnosability under the PMC model. We then show that the fault diagnosis problem for a t -diagnosable system under the SPMC model reduces to that of determining a maximum weighted b -matching in its diagnosis graph. Algorithm LABEL is then given to identify all the faulty vertices using the maximum b -matching of the diagnosis graph. Finally, using certain results from the theory of partitions of integers we establish the worst case complexity of our t -diagnosis algorithm. The complexity is much better than the worst case complexity of the Dahbura-Mason algorithm for the t -diagnosable problem under the PMC model. [ABSTRACT FROM AUTHOR]

Cops and Robbers games have been studied for the last few decades in computer science and mathematics. As in general pursuit evasion games, pursuers (cops) seek to capture evaders (robbers); however, players move in turn and are constrained to move on a discrete structure, usually a graph, and know the exact location of their opponent. In 2017, Bonato and MacGillivray [2] presented a general characterization of Cops and Robbers games in order for them to be globally studied. However, their model doesn't cover cases where stochastic events may occur, such as the robbers moving in a random fashion. In this paper we present a novel model with stochastic elements that we call a Generalized Probabilistic Cops and Robbers game (GPCR). A typical such game is one where the robber moves according to a probabilistic distribution, either because she is rather lost or drunk than evading, or because she is a robot. We present results to solve GPCR games, thus enabling one to study properties relating to the optimal strategies in large classes of Cops and Robbers games. Some classic Cops and Robbers games properties are also extended. [ABSTRACT FROM AUTHOR]

The exploration of one-factorizations of complete graphs is the foundation of some classical sports scheduling problems. One has to traverse the landscape of such one-factorizations by moving from one of those to a so-called neighbor one-factorization. This approach amounts to modifying locally the coloring associated with a one-factorization. We consider some particular types of modifications and describe various constructions which give one-factorizations which may be modified or not by these techniques. Among those are recoloring of bichromatic cycles, altering of optimally colored subcliques of even size, or recoloring of chordless lanterns. • One-factorizations of K 2 n are the foundation of some sports scheduling problems. • We define colorful subgraphs of one-factorizations that allow partial recolorings. • Several types of one-factorizations are defined. • The presence of the defined subgraphs on each type of factorization is investigated. [ABSTRACT FROM AUTHOR]

• We obtained a classification of the finiteness of certain P 5 -free k -critical graphs. • We obtained a complete characterization of 5-critical (P 5 , K 4) -free graphs. • The dual of Dilworth's Theorem was used in the study of k -critical graphs for the first time. Given two graphs H 1 and H 2 , a graph G is (H 1 , H 2) -free if it contains no induced subgraph isomorphic to H 1 or H 2. Let P t be the path on t vertices. A graph G is k -vertex-critical if G has chromatic number k but every proper induced subgraph of G has chromatic number less than k. The study of k -vertex-critical graphs for graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph class is finite, then there is a polynomial-time algorithm to decide if a graph in the class is (k − 1) -colorable. In this paper, we initiate a systematic study of the finiteness of k -vertex-critical graphs in subclasses of P 5 -free graphs. Our main result is a complete classification of the finiteness of k -vertex-critical graphs in the class of (P 5 , H) -free graphs for all graphs H on 4 vertices. To obtain the complete dichotomy, we prove the finiteness for four new graphs H using various techniques – such as Ramsey-type arguments and the dual of Dilworth's Theorem – that may be of independent interest. [ABSTRACT FROM AUTHOR]

The longest path problem on graphs is an NP-hard optimization problem, and as such, it is not known to have an efficient classical solution in the general case. This study develops two quadratic unconstrained binary optimization (QUBO) formulations of this well-known problem. The first formulation is based on an approach outlined by (Bauckhage et al., 2018) for the shortest path problem and follows simply from the principle of assigning positions on the path to vertices; using k | V | binary variables, this formulation will find the longest path that visits exactly k of a graph's | V | vertices, if such a path exists. As a point of theoretical interest, we present a second formulation based on degree constraints that is more complicated, but reduces the dependence of the number of variables on k to logarithmic; specifically, it requires | V | + 2 | E | ⌊ log 2 ⁡ k ⌋ + 3 | E | binary variables to encode the longest path problem. We adapt these basic formulations for several variants of the standard longest path problem. Scaling factors for penalty terms and preprocessing time required to construct the Q matrix representing the problem are made explicit in the paper. [ABSTRACT FROM AUTHOR]

A tessellation of a graph is a partition of its vertices into cliques. A tessellation cover of a graph is a set of tessellations that covers all of its edges, and the tessellation cover number, denoted by T (G) , is the size of a smallest tessellation cover. The t -tessellability problem aims to decide whether a graph G has T (G) ≤ t. The number of edges of a maximum induced star of G , denoted by s (G) , is a lower bound on T (G). In this work we define good tessellable graphs as the graphs G with T (G) = s (G) , and we introduce the corresponding good tessellable recognition (gtr) problem, which aims to decide whether G is a good tessellable graph. We show that gtr is NP -complete not only if T (G) can be obtained in polynomial time or s (G) is fixed, but also when the gap between T (G) and s (G) is large. We establish graph classes that present distinct computational complexities considering problems related to the parameters T (G) and s (G) , and we perform a comparative study of the gtr , t -tessellability , and star size problems, where the star size problem aims to decide whether the number of edges a maximum induced star of a graph is at least a given number. [ABSTRACT FROM AUTHOR]

The game of cops and robbers is a well-known game played on graphs. In this paper we consider the straight-ahead orientations of 4-regular quadrangulations of the torus and the Klein bottle and we prove that their cop number is bounded by a constant. We also show that the cop number of every k -regularly oriented toroidal grid is at most 13. [ABSTRACT FROM AUTHOR]

Sharkey, Kiss and others developed a dynamical approach to modelling epidemic disease on a contact graph by generating systems of first-order ordinary differential equations expressing the model dynamics [1,2] , which are solved to yield exact and deterministic modelling results. However, they left algorithmic generation (and solving) of systems and runtime assessment of the approach as an open question. To address this, we give an open source implementation that takes both a compartmental model and a contact graph as input and then generates and solves a system of equations exactly describing the dynamics of the system. Our implementation uses a moment closure result on single-vertex cutsets in the contact graph to reduce the number of equations required. In runtime experiments, we find that the implementation of the dynamical approach is almost always slower than a comparable Monte Carlo simulation in finding the expected state of the modelling system at a specified time. To complement our runtime evaluations, we give results and bounds on the number of equations required to describe a system as a function of the size of the compartmental model and input graph. We show that a natural extension of the moment closure result on single-vertex cutsets to larger cutsets is only possible for restricted projections of the model states on the cutset. We conclude that the dynamical approach is unlikely to be suitable unless exact, deterministic (rather than simulated) results are essential. • Details of an open source implementation of a dynamical approach to compartmental modelling on contact graphs • Asymptotic and runtime analyses of this dynamical approach • Evidence suggests that the approach is rarely more suitable than a stochastic simulation approach [ABSTRACT FROM AUTHOR]

Fractional (hyper-)graph theory is concerned with the specific problems that arise when fractional analogues of otherwise integer-valued (hyper-)graph invariants are considered. The focus of this paper is on fractional edge covers of hypergraphs. Our main technical result generalizes and unifies previous conditions under which the size of the support of fractional edge covers is bounded independently of the size of the hypergraph itself. We show how this combinatorial result can be used to extend previous tractability results for checking if the fractional hypertree width of a given hypergraph is ≤ k for some constant k. Moreover, we show a dual version of our main result for fractional hitting sets. [ABSTRACT FROM AUTHOR]

The connectivity of a graph is an important issue in graph theory and is also one of the most important factors in evaluating the reliability and fault tolerance of a network. A graph G is called m -edge-fault-tolerant strongly Menger (m -EFTSM for short) edge connected if there are min ⁡ { deg G − F ⁡ (x) , deg G − F ⁡ (y) } edge-disjoint paths between any two different vertices x and y in G − F for any F ⊆ E (G) with | F | ≤ m. In this paper, we give a necessary and sufficient condition of EFTSM edge connectivity on regular graphs. And we obtain several optimal results about EFTSM edge connectivity on (1, 2)-matching composition networks, each of which is constructed by connecting two graphs via one or two perfect matchings. As applications, we show that the class of n -dimensional hypercube-like networks (included hypercube, crossed cube et al.) are (n − 2) -EFTSM edge connected; show that the n -dimensional folded hypercube is (n − 1) -EFTSM edge connected, and show that the n -dimensional augmented cube is (2 n − 3) -EFTSM edge connected. The bounds (n − 2) , (n − 1) and (2 n − 3) are sharp. [ABSTRACT FROM AUTHOR]

Some microfluidic lab-on-chip devices contain modules whose function is to mix two fluids, called reactant and buffer, in desired proportions. In one of the technologies for fluid mixing the process can be represented by a directed acyclic graph whose nodes represent micro-mixers and edges represent micro-channels. A micro-mixer has two input channels and two output channels; it receives two fluid droplets, one from each input, mixes them perfectly, and produces two droplets of the mixed fluid on its output channels. Such a mixing graph converts a set I of input droplets into a set T of output droplets, where the droplets are specified by their reactant concentrations. The most fundamental algorithmic question related to mixing graphs is to determine, given an input set I and a target set T , whether there is a mixing graph that converts I into T. We refer to this decision problem as mix-reachability. While the complexity of this problem remains open, we provide a solution to its natural sub-problem, called perfect mixability , in which we ask whether, given a collection C of droplets, there is a mixing graph that mixes C perfectly, producing only droplets whose concentration is the average concentration of C. We provide a complete characterization of such perfectly mixable sets and an efficient algorithm for testing perfect mixability. Further, we prove that any perfectly mixable set has a perfect-mixing graph of polynomial size, and that this graph can be computed in polynomial time. [ABSTRACT FROM AUTHOR]

In this article, we study a variant of the minimum dominating set problem known as the minimum liar's dominating set (MLDS) problem. We prove that the MLDS problem is NP-hard in unit disk graphs. We point out that the approximation guarantee of 11 2 for the approximation algorithm for unit disk graphs proposed by Banerjee and Bhore (2019) [11] is not correct and we propose a simple O (n + m) time 7.31-factor approximation algorithm, where n and m are the number of vertices and edges, respectively, in the given unit disk graph. Finally, we prove that the MLDS problem admits a polynomial-time approximation scheme. [ABSTRACT FROM AUTHOR]

Basing on the two-player Voronoi game introduced by Ahn et al. [1] and the multi-player diffusion game introduced by Alon et al. [2] , we investigate the following one-round multi-player discrete Voronoi game on grids and trees. There are n players playing this game on a graph G = (V , E). Each player chooses an initial vertex from the vertex set of the graph and tries to maximize the size of the nearest vertex set. As the main result, we give sufficient conditions for the existence/non-existence of a pure-strategy Nash equilibrium in 4-player games on grids and only a constant gap leaves unknown. We further consider this game with more than 4 players and construct a family of strategy profiles, which are pure-strategy Nash equilibria on sufficiently narrow graphs. Besides, we investigate the game with 3 players on trees and design a linear time/space algorithm to decide the existence of a pure-strategy Nash equilibrium. [ABSTRACT FROM AUTHOR]

Diagnosability is an important metric for measuring the reliability of multiprocessor systems. The conditional diagnosability, which is more general than the classical diagnosability, is to measure the diagnosability of a multiprocessor system under the assumption that all of the neighbors of any node in the system cannot fail at the same time. This paper adopts the PMC model and outlines the common properties of a wide class of interconnection networks, called component-composition graphs (CCGs), to determine their conditional diagnosability by using the derived properties. As applications, the diagnosability of hypercube-like networks (including hypercubes, crossed cubes, Möbius cubes, twisted cubes, locally twisted cubes, generalized twisted cubes, and recursive circulants), and bubble-sort graphs, all of which belong to CCGs can be readily obtained. [ABSTRACT FROM AUTHOR]

With the development of scalability and application of multiprocessor system, the components of the system possibly become faulty. It is desirable to know the reliability of the system. However, the exact reliability of a complicated network system is usually difficult to determine. A typical approach is to decompose the system into smaller ones based on a graph-theory model in which nodes are assumed to fail independently with known probabilities to measure the subsystem-based reliability, which is defined as the probability that a fault-free subsystem of a specific size is still available when the system has faults. In this paper, we use the probability fault model to establish upper and lower bounds on the subsystem-based reliability of k -ary n -cube networks, by taking into account the intersection of no more than five or four subgraphs. In addition, some numerical simulations of the subsystem-based reliability of k -ary n -cube networks are conducted. [ABSTRACT FROM AUTHOR]

A deque automaton is a finite-state machine equipped with a deque memory tape. Such memory being more general than a queue or two stacks, we restrict consideration to quasi-real-time deque machines, for which we present useful normal forms. The closure properties of deque languages qualify them as an abstract family of languages but not a full one. The newly defined characteristic deque language CDL combines Dyck and AntiDyck (or FIFO) languages, and homomorphically characterizes the deque languages. The notion of deque graph from the graph drawing theory, well represents deque computations by means of a planar graph developed on a cylinder surface, with edges visualizing how deque symbols are inserted and removed. The drawing of deque computations on a cylinder is remindful of 3D models used in theoretical (bio)chemistry. We prove that a CDL can be defined in different ways: by a simple deque automaton, by labeled deque graphs, by cancellation rules, and by means of the shuffle and intersection of simpler languages. The labeled deque graph represents the syntax structure of a word. [ABSTRACT FROM AUTHOR]

The minimum size of the largest component of a network with faults is a useful parameter to make a full evaluation of this network and it is helpful for estimating some other parameters in graph theory. In this paper, we focus on discussing the minimum size of the largest component of star graph S n which contains faulty edges. Specifically, we show that there exists at most one, two, three, four, five vertices beyond the largest component of S n − F with F ⊆ E (S n) and | F | ≤ 2 n − 5 , 3 n − 8 , 4 n − 11 , 5 n − 15 , 6 n − 19 respectively. As applications, we study the g -extra edge connectivity of S n for 1 ≤ g ≤ 5 , and study the strong Menger edge connectivity of S n − F with F ∈ E (S n). [ABSTRACT FROM AUTHOR]

A total domatic k-partition of a graph is a partition of its vertex set into k subsets such that each intersects the open neighborhood of each vertex. The maximum k for which a total domatic k -partition exists is known as the total domatic number of a graph G , denoted by d t (G). We extend considerably the known hardness results by showing it is Image 1 -complete to decide whether d t (G) ≥ 3 where G is a bipartite planar graph of bounded maximum degree. Similarly, for every k ≥ 3 , it is Image 1 -complete to decide whether d t (G) ≥ k , where G is split or k -regular. In particular, these results complement recent combinatorial results regarding d t (G) on some of these graph classes by showing that the known results are, in a sense, best possible. Finally, for general n -vertex graphs, we show the problem is solvable in 2 n n O (1) time, and derive even faster algorithms for special graph classes. [ABSTRACT FROM AUTHOR]

Rearrangeable Clos networks have been studied for a long time due to their many applications, as well as their theoretical interest. In a rearrangeable Clos network, a newly requested connection may be blocked by existing connections. However, this blocking is eliminated by adequately rearranging some other existing connections. In this operation, an interesting topic is the sufficient number of rearrangements required to eliminate the blocking. Despite previous studies, the sufficient number of rearrangements has only been found for limited cases and has not been completely determined for generic parameter values. This paper analyses the number of rearrangements using the connection chain concept, which clearly and efficiently represents a sequence of connections to be rearranged. The analysis assumes the employment of a rearrangement algorithm, which eliminates the blocking using the shortest connection chain. The usage of the shortest connection chain results in the minimum number of rearrangements. As a result, this paper determines a new bound on the number of rearrangements for a parameter range that has not been considered in any previous studies. In addition, this paper examines the condition for which the system is unblocked via one rearrangement. [ABSTRACT FROM AUTHOR]

In this work we determine the metric dimension of Z n × Z n × Z n as ⌊ 3 n / 2 ⌋ for all n ≥ 2. We prove this result by investigating a variant of Mastermind. Mastermind is a famous two-player game that has attracted much attention in the literature in recent years. In particular we consider the static (also called non-adaptive) black-peg variant of Mastermind. The game is played by a codemaker and a codebreaker. Given c colors and p pegs, the principal rule is that the codemaker has to choose a secret by assigning colors to the pegs, i.e., the secret is a p -tuple of colors, and the codebreaker asks a number of questions all at once. Like the secret, a question is a p -tuple of colors chosen from the c available colors. The codemaker then answers all of those questions by telling the codebreaker how many pegs in each question are correctly colored. The goal is to find the minimal number of questions that allows the codebreaker to determine the secret from the received answers. We present such a strategy for this game for p = 3 pegs and an arbitrary number c ≥ 2 of colors using ⌊ 3 c / 2 ⌋ + 1 questions, which we prove to be both feasible and optimal. The minimal number of questions required for p pegs and c colors is easily seen to be equal to the metric dimension of Z c p plus 1 which proves our main result. [ABSTRACT FROM AUTHOR]

• We embed various cycles in an n-dimensional folded hypercube interconnection network with two adjacent faulty vertices. • Even lengths and odd lengths of cycles have been proposed in folded hypercubes with two adjacent faulty vertices, respectively. • Our study improves the previously reported result with respect to the longest length of odd cycle in non-bipartite folded hypercube. It has been shown that the n -dimensional folded hypercube topology (F Q n for short) is bipartite for every odd n ≥ 3 , and which is non-bipartite for every even n ≥ 2 [9]. In this paper, let { f 1 , f 2 } denote the set of a pair of adjacent faulty vertices in F Q n. Then, we show the lengths of cycles embedding in F Q n − { f 1 , f 2 } as follows: 1. For n ≥ 3 , F Q n − { f 1 , f 2 } contains a fault-free cycle of every even length from 4 to 2 n − 2 ; 2. For every even n ≥ 4 , F Q n − { f 1 , f 2 } contains a fault-free cycle of every odd length from n + 1 to 2 n − 3. As a contribution, our study improves the result of [7] with respect to the longest length of cycle embedding in non-bipartite F Q n , where the embedded longest length of cycle only up to 2 n − 2 × 2 − 1 = 2 n − 5 in F Q n − { f 1 , f 2 }. [ABSTRACT FROM AUTHOR]

In the Firefighter problem, introduced by Hartnell in 1995, a fire spreads through a graph while a player chooses which vertices to protect in order to contain it. In this paper, we focus on the case of trees and we consider as well the Fractional Firefighter game where the amount of protection allocated to a vertex lies between 0 and 1. While most of the work in this area deals with a constant amount of firefighters available at each turn, we consider three research questions which arise when including the sequence of firefighters as part of the instance. We first introduce the online version of both Firefighter and Fractional Firefighter , in which the number of firefighters available at each turn is revealed over time. We show that a greedy algorithm on finite trees is 1/2-competitive for both online versions, which generalises a result previously known for special cases of Firefighter. We also show that the optimal competitive ratio of online Firefighter ranges between 1/2 and the inverse of the golden ratio. Next, given two firefighter sequences, we discuss sufficient conditions for the existence of an infinite tree that separates them, in the sense that the fire can be contained with one sequence but not with the other. To this aim, we study a new purely numerical game called targeting game. Finally, we give sufficient conditions for the fire to be contained, expressed as the asymptotic comparison of the number of firefighters and the size of the tree levels. [ABSTRACT FROM AUTHOR]

In spectral graph theory, the Cheeger inequality gives upper and lower bounds of edge expansion in normal graphs in terms of the second eigenvalue of the graph's Laplacian operator. Recently this inequality has been extended to undirected hypergraphs and directed normal graphs via a non-linear operator associated with a diffusion process in the underlying graph. In this work, we develop a unifying framework for defining a diffusion operator on a directed hypergraph with stationary vertices, which is general enough for the following two applications. 1. Cheeger's inequality for directed hyperedge expansion. 2. Quadratic optimization with stationary vertices in the context of semi-supervised learning. Despite the crucial role of the diffusion process in spectral analysis, previous works have not formally established the existence of the corresponding diffusion processes. In this work, we give a proof framework that can indeed show that such diffusion processes are well-defined. In the first application, we use the spectral properties of the diffusion operator to achieve the Cheeger's inequality for directed hyperedge expansion. In the second application, the diffusion operator can be interpreted as giving a continuous analog to the subgradient method, which moves the feasible solution in discrete steps towards an optimal solution. [ABSTRACT FROM AUTHOR]

For a fixed number of colors, we show that, in node-weighted split graphs, cographs, and graphs of bounded tree-width, one can determine in polynomial time whether a proper list-coloring of the vertices of a graph such that the total weight of vertices of each color equals a given value in each part of a fixed partition of the vertices exists. We also show that this result is tight in some sense, by providing hardness results for the cases where any one of the assumptions does not hold. The edge-coloring variant is also studied, as well as special cases of cographs and split graphs. [ABSTRACT FROM AUTHOR]

Given a network property or a data structure, a local certification is a labeling that allows to efficiently check that the property is satisfied, or that the structure is correct. The quality of a certification is measured by the size of its labels: the smaller, the better. This notion plays a central role in self-stabilization, because the size of the certification is a lower bound (and often an upper bound) on the memory needed for silent self-stabilizing construction of distributed data structures. When it comes to the size of the certification labels, one can identify three important regimes: the properties for which the optimal size is polynomial in the number of vertices of the graph, the ones that require only polylogarithmic size, and the ones that can be certified with a constant number of bits. The first two regimes are well studied, with several upper and lower bounds, specific techniques, and active research questions. On the other hand, the constant regime has never been really explored. The main contribution of this paper is the first non-trivial lower bound for this constant regime. More precisely, we show that by using certification on just one bit (a binary certification), one cannot certify k -colorability for k ≥ 3. To do so, we develop a new technique, based on the notion of score, and both local symmetry arguments and a global parity argument. We hope that this technique will be useful for establishing stronger results. We complement this result with an upper bound for a related problem, illustrating that in some cases one can do better than the natural upper bound. [ABSTRACT FROM AUTHOR]

In 2011, Danicic et al. introduced an elegant generalization of the notion of control dependence for any directed graph. They also proposed an algorithm computing the weak control-closure of a subset of graph vertices and performed a paper-and-pencil proof of its correctness. We have performed its machine-checked proof in the Coq proof assistant. This paper also presents a novel, more efficient algorithm called lDFS to compute weak control-closure taking benefit of intermediate propagation results of previous iterations in order to accelerate the following ones. This optimization makes the design of the algorithm more complex and requires subtle loop invariants for its proof. lDFS has been formalized and mechanically proven in the Why3 verification tool. To investigate the impact of several possible optimizations and compare the performances of different versions of the algorithm, we perform experiments on arbitrary generated graphs with up to hundreds of thousands of vertices. They demonstrate that the proposed algorithm remains practical for real-life programs and significantly outperforms all considered versions of Danicic's initial technique. [ABSTRACT FROM AUTHOR]

Distance-hereditary graphs are in important graph class in graph theory, as they are well-placed in the graph class hierarchy and permit many algorithmic results. We investigate structural and algorithmic advantages of a directed version of this well-researched graph class. Since the previously defined distance-hereditary digraphs do not permit a recursive structure, we define directed twin-distance-hereditary graphs, which can be constructed by several twin and pendant vertex operations analogously to undirected distance-hereditary graphs and which still preserves the distance hereditary property. We give a characterization by forbidden induced subdigraphs and place the class in a hierarchy comparing it to related classes. We further show algorithmic advantages concerning directed width parameters, directed graph coloring and some other well-known digraph problems which are NP-hard in general, but computable in polynomial or even linear time on twin-distance-hereditary digraphs. This includes computability of directed path-width and tree-width in linear time and the directed chromatic number in polynomial time. From our result that directed twin-distance-hereditary graphs have directed clique-width at most 3 it follows by Courcelle's theorem on directed clique-width that we can compute every graph problem describable in monadic second-order logic on quantification over vertices and vertex sets as well as some further problems like Hamiltonian Path/Cycle in polynomial time. [ABSTRACT FROM AUTHOR]

Abstract A set of vertices in a graph is c-colorable if the subgraph induced by the set has a proper c -coloring. In this paper, we study the problem of finding a step-by-step transformation (called a reconfiguration sequence) between two c -colorable sets in the same graph. This problem generalizes the well-studied Independent Set Reconfiguration problem. As the first step toward a systematic understanding of the complexity of this general problem, we study the problem on classes of perfect graphs. We first focus on interval graphs and give a combinatorial characterization of the distance between two c -colorable sets. This gives a linear-time algorithm for finding an actual shortest reconfiguration sequence for interval graphs. Since interval graphs are exactly the graphs that are simultaneously chordal and co-comparability, we then complement the positive result by showing that even deciding reachability is PSPACE-complete for chordal graphs and for co-comparability graphs. The hardness for chordal graphs holds even for split graphs. We also consider the case where c is a fixed constant and show that in such a case the reachability problem is polynomial-time solvable for split graphs but still PSPACE-complete for co-comparability graphs. The complexity of this case for chordal graphs remains unsettled. As by-products, our positive results give the first polynomial-time solvable cases (split graphs and interval graphs) for Feedback Vertex Set Reconfiguration. [ABSTRACT FROM AUTHOR]

Abstract We study the parameterized complexity of domination problems on sparse graphs and beyond. The nowhere dense classes of graphs have been proposed as the main model for sparseness that can be utilized algorithmically. The class of d -degenerate graphs is not nowhere dense, yet domination remains fixed-parameter tractable. Both nowhere dense classes of graphs and d -degenerate graph classes are biclique-free classes, meaning there is an integer t such that no graph in the class contains K t , t as a subgraph. In this paper we show that various domination problems are fixed-parameter tractable on biclique-free classes of graphs. Our algorithms are simple and rely on results from extremal graph theory that bound the number of edges in a t -biclique free graph. In particular, the problems k -Dominating Set , Connected k -Dominating Set , Independent k -Dominating Set and Minimum Weight k -Dominating Set are shown to be FPT, when parameterized by t + k , on graphs not containing K t , t as a subgraph. With the exception of Connected k -Dominating Set all described algorithms are linear in the size of the input graph. [ABSTRACT FROM AUTHOR]

Abstract We investigate the complexity of four decision problems dealing with the uniqueness of a solution in a graph: "Uniqueness of an r -Locating–Dominating Code with bounded size" (U-LDC r), "Uniqueness of an Optimal r -Locating–Dominating Code" (U-OLDC r), "Uniqueness of an r -Identifying Code with bounded size" (U-IdC r), "Uniqueness of an Optimal r -Identifying Code" (U-OIdC r), for any fixed integer r ≥ 1. In particular, we describe a polynomial reduction from "Unique Satisfiability of a Boolean formula" (U-SAT) to U-OLDC r , and from U-SAT to U-OIdC r ; for U-LDC r and U-IdC r , we can do even better and prove that their complexity is the same as that of U-SAT, up to polynomials. Consequently, all these problems are NP -hard, and U-LDC r and U-IdC r belong to the class DP. [ABSTRACT FROM AUTHOR]

Abstract The balanced hypercube was proposed as a novel interconnection network for large-scale parallel systems. It is known that the balanced hypercube is edge-bipancyclic. Given a set of edges P with | P | ≤ n − 1 and two vertices x and y in different bipartite sets, we show that there exists a Hamiltonian path from x to y passing through P in B H n if and only if P is a linear forest and, neither x nor y is an internal vertex of P , and x and y are not end-vertices of a component of P simultaneously. Consequently, the balanced hypercube contains a Hamiltonian cycle passing through a set P of at most n prescribed edges if and only if P is a linear forest. Moreover, our result improves some known results. [ABSTRACT FROM AUTHOR]

Highlights • We study a refined measure for the fault-tolerance of a network, called h -super connectivity. • We determine h -super connectivity of the generalized star network. • We generalize some known results. Abstract This paper considers the conditional fault tolerance, h -super connectivity κ h and h -super edge-connectivity λ h of the hierarchical cubic network H C N n , an attractive alternative network to the hypercube, and shows κ h (H C N n) = λ h (H C N n) = 2 h (n + 1 − h) for any h with 0 ≤ h ≤ n − 1. The results imply that at least 2 h (n + 1 − h) vertices or edges have to be removed from H C N n to make it disconnected with no vertices of degree less than h , and generalize some known results. [ABSTRACT FROM AUTHOR]

Abstract Fault diagnosis of systems is an important area of study in the design and maintenance of multiprocessor systems. A new measure for fault diagnosis of systems, namely, h -edge tolerable diagnosability, is the maximum number of faulty nodes that a system G can guarantee to locate when the number of faulty links does not exceed h , denoted by t h e (G). Particularly, t 0 e (G) is the traditional diagnosability of G. Chang et al. (2005) [5] determined the traditional diagnosabilities of regular graphs. In this paper, we establish the h -edge tolerable diagnosabilities of regular graphs under the PMC model and the MM⁎ model, which extends their results and provides a more precise characterization for the fault diagnosis capability of regular graphs. As applications, the h -edge tolerable diagnosabilities of many networks are determined under the PMC model and the MM⁎ model. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we generalize the concept of complete coloring and achromatic number to 2-edge-colored graphs and signed graphs. We give some useful relationships between different possible definitions of such achromatic numbers and prove that computing any of them is NP-complete. [ABSTRACT FROM AUTHOR]

Abstract The matching preclusion number of a graph G , denoted by mp (G) , is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. In this paper, we first give some sharp upper and lower bounds of matching preclusion number. Next, graphs with large and small matching preclusion number are characterized, respectively. In the end, we investigate some extremal problems and the Nordhaus–Gaddum-type relations on matching preclusion number. [ABSTRACT FROM AUTHOR]

Abstract We study the Moran process as adapted by Lieberman, Hauert and Nowak. This is a model of an evolving population on a graph or digraph where certain individuals, called "mutants" have fitness r and other individuals, called "non-mutants" have fitness 1. We focus on the situation where the mutation is advantageous, in the sense that r > 1. A family of digraphs is said to be strongly amplifying if the extinction probability tends to 0 when the Moran process is run on digraphs in this family. The most-amplifying known family of digraphs is the family of megastars of Galanis et al. We show that this family is optimal, up to logarithmic factors, since every strongly-connected n -vertex digraph has extinction probability Ω (n − 1 / 2). Next, we show that there is an infinite family of undirected graphs, called dense incubators, whose extinction probability is O (n − 1 / 3). We show that this is optimal, up to constant factors. Finally, we introduce sparse incubators, for varying edge density, and show that the extinction probability of these graphs is O (n / m) , where m is the number of edges. Again, we show that this is optimal, up to constant factors. [ABSTRACT FROM AUTHOR]

Abstract Plane increasing trees are rooted labeled trees embedded into the plane such that the sequence of labels is increasing on any branch starting at the root. Relaxed binary trees are a subclass of unlabeled directed acyclic graphs. We construct a bijection between these two combinatorial objects and study the therefrom arising connections of certain parameters. Furthermore, we show central limit theorems for two statistics on leaves. We end the study by considering more than 20 subclasses and their bijective counterparts. Many of these subclasses are enumerated by known counting sequences, and thus enrich their combinatorial interpretation. [ABSTRACT FROM AUTHOR]

Abstract The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has no perfect matchings or almost-perfect matchings. For many interconnection networks, the matching preclusion number is equal to the minimum degree of a vertex in the network, and the sets of edges attaining the minimum are precisely those incident to a single vertex of minimum degree; we say such networks are super matched. In this paper we derive upper and lower bounds for the matching preclusion number for networks constructed using a variety of binary graph operations, and give sufficient conditions for such networks to be super matched. [ABSTRACT FROM AUTHOR]

Abstract We develop efficient parameterized, with additive error, approximation algorithms for the (Connected) r -Domination problem and the (Connected) p -Center problem for unweighted and undirected graphs. Given a graph G , we show how to construct a (connected) (r + O (μ)) -dominating set D with | D | ≤ | D ⁎ | efficiently. Here, D ⁎ is a minimum (connected) r -dominating set of G and μ is our graph parameter, which is the tree-breadth or the cluster diameter in a layering partition of G. Additionally, we show that a + O (μ) -approximation for the (Connected) p -Center problem on G can be computed in polynomial time. Our interest in these parameters stems from the fact that in many real-world networks, including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others, and in many structured classes of graphs these parameters are small constants. [ABSTRACT FROM AUTHOR]

Abstract The significant increase in the number of processors of the multiprocessor system increases its vulnerability to component failures. Diagnosability is an important indicator in measuring the reliability of interconnection networks. The g -good-neighbor conditional faulty set is a faulty set that each fault-free vertex is adjacent to at least g fault-free vertices. The g -good-neighbor conditional diagnosability gives the maximum cardinality of g -good-neighbor conditional faulty set that the system is guaranteed to identify. This paper we establish the g -good-neighbor conditional diagnosability of the crossed cube C Q n under the PMC and MM* model. [ABSTRACT FROM AUTHOR]

Abstract Domination is one of the classical subjects in structural graph theory and in graph algorithms. The Minimum Dominating Set problem and many of its variants are NP-complete and have been studied from various algorithmic perspectives. One of those variants called irredundance is highly related to domination. For example, every minimal dominating set of a graph G is also a maximal irredundant set of G. In this paper we study the enumeration of the maximal irredundant sets of a claw-free graph. We show that an n -vertex claw-free graph has O (1.9341 n) maximal irredundant sets and these sets can be enumerated in the same time. We complement the aforementioned upper bound with a lower bound by providing a family of graphs having 1.5848 n maximal irredundant sets. [ABSTRACT FROM AUTHOR]

Abstract For any rectangular grid graph with grid units each potentially having a diagonal edge, we propose a data structure that is constructible in time linear in the number of grid units in the graph and supports linear-time queries of a shortest path between any pair of vertices in the graph. Setting the position of grid units having a diagonal edge appropriately, we can use this data structure to solve a local variant of the longest common subsequence problem or certain related problems in linear time. [ABSTRACT FROM AUTHOR]

Abstract A pair of agents (robots) are moving in a graph with the goal of meeting at the same node or while traversing the same edge. An asynchronous adversary knows the prescribed walks of the two agents and is in complete control of the speed of each agent during its walk. We provide a complete characterization of pairs of walks that enforce rendezvous against an asynchronous adversary after traversing a given number of edges. The characterization is efficient in that it can be checked in polynomial time. We argue that the certificate of rendezvous enforcement that is produced by the checking algorithm contains a wealth of information on why rendezvous is enforced. [ABSTRACT FROM AUTHOR]

Abstract Implicit graph algorithms deal with the characteristic function χ E of the edge set E of a graph G = (V , E). Encoding the nodes by binary vectors, χ E can be represented by an Ordered Binary Decision Diagram (OBDD) which is a well known data structure for Boolean functions. OBDD-based graph algorithms solve graph optimization problems by mainly using functional operations and are a heuristic approach to cope with massive graphs. These algorithms heavily rely on a compact representation of the underlying Boolean functions which is why all previously known OBDD-based algorithms are deterministic since random functions are not compressible in general. Here, the first randomized OBDD-based algorithms are presented where random functions with limited independence are used to overcome the large representation size. On the theoretical part, we investigate the size of OBDDs representing k -wise independent random functions. In addition, we give a construction of almost k -wise independent random functions by means of a random OBDD generation and show an almost matching lower bound of the OBDD size representing such random functions. On the algorithmic part, randomization often facilitates the design of simple algorithms which in the context of OBDD-based algorithms means a small number of functional operations and as few input variables of the used Boolean functions as possible. We present two randomized implicit algorithms: A randomized minimum spanning tree algorithm and a maximal matching algorithm. The matching algorithm needs O (log 3 ⁡ | V |) functional operations in expectation and uses functions with at most 3 log ⁡ | V | variables which is both better than the best known deterministic algorithms w.r.t. functional operations and variables. The algorithm may be of independent interest. The experimental evaluation of the algorithms shows that they outperform known OBDD-based algorithms for the maximal matching problem and the minimum spanning tree problem. [ABSTRACT FROM AUTHOR]