Search

In this paper, we study Horn formulas from the perspective of read-once resolution refutations (RORs). A Horn formula is a Boolean formula in conjunctive normal form (CNF), in which each clause contains at most one positive literal. Horn formulas are used in a number of domains, including program verification, logic programming, and econometrics. In particular, deduction in ProLog is based on unification. Unification is based on resolution and instantiation. Resolution is a system used to prove the infeasibility of Boolean formulas. It is important to note that resolution is both sound and complete. However, resolution is inefficient in the following sense: There exist CNF formulas with resolution refutations whose lengths are bounded below by an exponential function of the input size. At the same time, these formulas admit shorter (polynomially bounded) proofs of infeasibility in other proof systems, such as Frege Systems. Despite this inefficiency, resolution is simple and easy to implement and hence used in a wide variety of theorem provers. In this paper, we study two variants of resolution. These are read-once resolution (ROR) and read-once unit resolution (UROR). Both ROR and UROR are sound. However, they are incomplete since there exist infeasible Boolean formulas which do not have either an ROR or a UROR. In this paper, we look at the problems of determining if a Horn formula has an ROR or a UROR. We also examine the problem of finding the optimal length ROR of a Horn formula from both the computational complexity and the approximation perspectives. Finally, we analyze the copy complexity of Horn formulas with respect to URORs. [ABSTRACT FROM AUTHOR]

An equitable coloring of a graph G is a proper vertex coloring of G such that the sizes of any two color classes differ by at most one. In the paper, we pose a conjecture that offers a gap-one bound for the smallest number of colors needed to equitably color every block graph. In other words, the difference between the upper and the lower bounds of our conjecture is at most one. Thus, in some sense, the situation is similar to that of chromatic index, where we have the classical theorem of Vizing and the Andersen–Goldberg–Seymour conjecture for multigraphs. The results obtained in the paper support our conjecture. More precisely, we verify it in the class of block graphs in which each vertex belongs to a maximum independent set. We also show that the conjecture is true for block graphs which contain a vertex that does not lie in an independent set of size larger than two. Finally, we verify the conjecture for some symmetric-like block graphs. In order to derive our results we obtain structural characterizations of block graphs from these classes. [ABSTRACT FROM AUTHOR]

In this paper, we study algorithmic questions concerning products of matrices and their consequences for recognition algorithms for polyhedra. The 1- product of matrices S 1 ∈ R m 1 × n 1 , S 2 ∈ R m 2 × n 2 is a matrix in R (m 1 + m 2) × (n 1 n 2) whose columns are the concatenation of each column of S 1 with each column of S 2. The k - product generalizes the 1-product, by taking as input two matrices S 1 , S 2 together with k − 1 special rows of each of those matrices, and outputting a certain composition of S 1 , S 2 . Our first result is a polynomial time algorithm for the following problem: given a matrix S , is S a k -product of some matrices, up to permutation of rows and columns? Our algorithm is based on minimizing a symmetric submodular function that expresses mutual information from information theory. Our study is motivated by a close link between the 1-product of matrices and the Cartesian product of polytopes, and more generally between the k -product of matrices and the glued product of polytopes. These connections rely on the concept of a slack matrix, which gives an algebraic representation of classes of affinely equivalent polytopes. The slack matrix recognition problem is the problem of determining whether a given matrix is a slack matrix. This is an intriguing problem whose complexity is unknown. Our algorithm reduces the problem to instances which cannot be expressed as k -products of smaller matrices. In the second part of the paper, we give a combinatorial interpretation of k -products for two well-known classes of polytopes: 2-level matroid base polytopes and stable set polytopes of perfect graphs. We also show that the slack matrix recognition problem is polynomial-time solvable for such polytopes. Those two classes are special cases of 2-level polytopes, for which we conjecture that the slack matrix recognition problem is polynomial-time solvable. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the performance of message-passing algorithms for the weighted min–max flow (WMMF) problem which was introduced by Ichimori et al. (1980). WMMF was well studied in combinational optimization, as it provides important applications in time transportation problem and the storage management problem. We develop a message-passing algorithm called min–max belief propagation (BP) for determining the optimal solution of WMMF. As the main result of this paper, we prove that for a digraph of size n , BP converges to the optimal solution within O (n 3) time after O (n) iterations if the optimal solution of the underlying min–max flow problem instance is unique. To the best of our knowledge, the fastest polynomial time algorithm for WMMF runs in essentially O (n 6) time among the known algorithms, where n is the number of vertices. On the other hand, it is one of a very few instances where BP is proved correct with fully-polynomial running time. [ABSTRACT FROM AUTHOR]

Several concepts that model processes of spreading (of information, disease, objects, etc.) in graphs or networks have been studied. In many contexts, we assume that some vertices of a graph G are contaminated initially, before the process starts. By the q -forcing rule, a contaminated vertex having at most q uncontaminated neighbors enforces all the neighbors to become contaminated, while by the p -percolation rule, an uncontaminated vertex becomes contaminated if at least p of its neighbors are contaminated. If given a set S of initially contaminated vertices all vertices eventually become contaminated when continuously applying the q -forcing rule (respectively the p -percolation rule), S is called a q -forcing set (respectively, a p -percolating set) in G. In this paper, we consider sets S that are at the same time q -forcing sets and p -percolating sets, and call them (p , q) -spreading sets. Given positive integers p and q , the minimum cardinality of a (p , q) -spreading set in G is a (p , q) -spreading number, σ (p , q) (G) , of G. While q -forcing sets have been studied in a dozen of papers, the decision version of the corresponding graph invariant has not been considered earlier, and we fill the gap by proving its NP-completeness. This, in turn, enables us to prove the NP-completeness of the decision version of the (p , q) -spreading number in graphs for an arbitrary choice of p and q. Again, for every p ∈ N and q ∈ N ∪ { ∞ } , we find a linear-time algorithm for determining the (p , q) -spreading number of a tree, where in the case p ≥ 2 we apply Riedl's algorithm from [Largest and smallest minimal percolating sets in trees, Electron. J. Combin. 19 (2012) Paper 64] on p -percolation in trees. In addition, we present a lower and an upper bound on the (p , q) -spreading number of a tree and characterize extremal families of trees. In the case of square grids, we combine some results of Bollobás from [The Art of Mathematics: Coffee Time in Memphis. Cambridge Univ. Press, New York, 2006], and the AIM Minimum Rank-Special Graphs Work Group from [Zero forcing sets and the minimum rank of graphs, Linear algebra Appl. 428 2008 1628–1648], and new results on (2 , 1) -spreading and (4 , q) -spreading to obtain σ (p , q) (P m □ P n) for all (p , q) ∈ (N ∖ { 3 }) × (N ∪ { ∞ }) and all m , n ∈ N. [ABSTRACT FROM AUTHOR]

The concept of conflict-free connection coloring of graphs was introduced by Czap et al. in 2018. It has been the subject of several papers, which is closely related with conflict-free coloring of hypergraphs. In this survey we bring together most of the results and papers on this topic. We begin with an introduction, and then try to organize the work into three categories, conflict-free connection number, strong conflict-free connection number and conflict-free vertex-connection number. This survey also contains some conjectures, open problems and questions. [ABSTRACT FROM AUTHOR]

This paper deals with the complexity of some natural graph problems parameterized by some measures that are restrictions of clique-width, such as modular-width and neighborhood diversity. We introduce a novel parameter, called iterated type partition number, that can be computed in linear time and nicely places between modular-width and neighborhood diversity. We prove that the Equitable Coloring problem is W [ 1 ] -hard when parameterized by the iterated type partition number. This result extends to modular-width, answering an open question on the complexity of Equitable Coloring when parameterized by modular-width. On the contrary, we show that the Equitable Coloring problem is FPT when parameterized by neighborhood diversity. Furthermore, we present a scheme for devising FPT algorithms parameterized by iterated type partition number, which enables us to find optimal solutions for several graph problems. As an example, in this paper, we present algorithms parameterized by the iterated type partition number of the input graph for some generalized versions of the Maximum Clique , Minimum Graph Coloring , (Total) Minimum Dominating Set , Minimum Vertex Cover and Maximum Independent Set problems. Each algorithm outputs not only the optimal value but also the optimal solution. We stress that while the considered problems are already known to be FPT with respect to modular-width, the novel algorithms are both simpler and more efficient. We finally show that the proposed scheme can be used to devise polynomial kernels, with respect to iterated type partition number, for the decisional version of most of the problems mentioned above. [ABSTRACT FROM AUTHOR]

This paper studies three edge-removing games on graphs. In each game, there are two players and a simple graph G at the beginning. The players take turns removing at least one edge of a certain type from the current graph. The one who cannot move loses the game, and the other one, who plays the last move, wins. This paper gives results for these games on some interesting classes of graphs by either computing their Grundy numbers or proposing winning strategies. [ABSTRACT FROM AUTHOR]

The Terrain Guarding problem, a variant of the famous Art Gallery problem, has garnered significant attention over the last two decades in Computational Geometry from the viewpoint of complexity and approximability. Both the continuous and discrete versions of the problem were shown to be NP-Hard in King and Krohn (2010) and to admit a PTAS (Krohn et al., 2014; Friedrichs et al., 2016). The biggest unsolved question regarding this problem is if it is fixed-parameter tractable with respect to the size of the guard set. In this paper, we present two theorems that establish a relationship between a restricted case of the ONE-SIDED TERRAIN GUARDING problem and the Clique Cover problem in chordal graphs. These theorems were proved in Katz and Roisman (2008) for a special class of terrains called orthogonal terrains and were used to present a FPT algorithm with respect to the parameter that we require for DISCRETE ORTHOGONAL TERRAIN GUARDING in Ashok et al. (2018). We hope that the results obtained in this paper can, in future work, be used to produce such an algorithm for Discrete Terrain Guarding. [ABSTRACT FROM AUTHOR]

In the original article (Gutman et al., 2014), the authors state that the Wiener index (total distance) of an Eulerian graph is maximized by the cycle. We explain that the initial proof contains a flaw and note that it is a corollary of a result by Plesník, since an Eulerian graph is 2-edge-connected. The same incorrect proof is used in two referencing papers, (Liu et al., 2019) and (Cai et al., 2021). We give proofs of the main results of those papers and the 2-edge-connected analogues. [ABSTRACT FROM AUTHOR]

Word-representable graphs, which are the same as semi-transitively orientable graphs, generalize several fundamental classes of graphs. In this paper we propose a novel approach to study word-representability of graphs using a technique of homomorphisms. As a proof of concept, we apply our method to show word-representability of the simplified graph of overlapping permutations that we introduce in this paper. For another application, we obtain results on word-representability of certain subgraphs of simplified de Bruijn graphs that were introduced recently by Petyuk and studied in the context of word-representability. [ABSTRACT FROM AUTHOR]

Paintability of graphs, which is also called online choosability of graphs, was introduced by Schauz and by Zhu in 2009, and has been studied in point of the difference from choosability of graphs. Compared with the choice number and the chromatic number, it is much more difficult to determine the paint number of a given graph. For example, even the 3-paintable complete bipartite graphs have not been characterized yet. In this paper, we focus on the paintability of complete bipartite graphs, especially m -paintability of K m + 1 , r. Let r OL (m) denote the least integer r such that K m + 1 , r is not m -paintable. In this paper, we determine the order of r OL (m) as r OL (m) = Θ (m m − 1). Let r (m) denote the least r such that K m + 1 , r is not m -choosable, for which Hoffman and Johnson Jr. determined as r (m) = m m − (m − 1) m = Θ (m m). As a corollary, we can show that r OL (m) / r (m) tends to 0 when m goes to infinity. [ABSTRACT FROM AUTHOR]

The chromatic index , χ ′ (G) , is the smallest integer k for which a graph G has a proper edge coloring. The Classification Problem involves determining whether a graph G is Class 1 ( χ ′ (G) = Δ (G)) or Class 2 ( χ ′ (G) = Δ (G) + 1). It is known that subgraph-overfull graphs must be Class 2. In this paper we are concerned with the Classification Problem for split graphs G [ Q ∪ S ] where Q is a clique and S is an independent set. When Δ (G) is odd, G is known to be Class 1. The original proof presented by Chen et al. (1995) has a minor flaw which we detail in this paper while also clarifying that it does not compromise their result. We prove that their technique can be adapted in a non-trivial way to show that some split graphs with even Δ (G) are also Class 1. We show that to solve the Classification Problem for split graphs it suffices to consider that all vertices in Q have degree Δ (G). Considering the subset X of S of the vertices of degree at most Δ (G) / 2 , we show that if the neighborhood of X has at least ⌊ | Q | / 2 ⌋ vertices, then G is Class 1; in the remaining cases we characterize the subgraph-overfull split graphs. • Correction of a flaw in the proof that odd maximum degree split graphs are Class 1. • Proof that certain split graphs with even maximum degree are Class 1. • Characterization of the split graphs which are subgraph-overfull, and thus Class 2. [ABSTRACT FROM AUTHOR]

In this paper, we are interested in algorithms that take in input an arbitrary graph G , and that enumerate in output all the (inclusion-wise) maximal "subgraphs" of G which fulfil a given property Π. All over this paper, we study several different properties Π , and the notion of subgraph under consideration (induced or not) will vary from a result to another. More precisely, we present efficient algorithms to list all maximal split subgraphs, maximal induced cographs and maximal threshold graphs of a given input graph. All the algorithms presented here run in polynomial delay, and moreover for split graphs it only requires polynomial space. In order to develop an algorithm for maximal split (edge-)subgraphs, we establish a bijection between the maximal split subgraphs and the maximal stable sets of an auxiliary graph. For cographs and threshold graphs, the algorithms rely on a framework recently introduced by Conte & Uno (2019) called Proximity Search. Finally we consider the extension problem, which consists in deciding if there exists a maximal induced subgraph satisfying a property Π that contains a set of prescribed vertices and that avoids another set of vertices. We show that this problem is NP-complete for every non-trivial hereditary property Π. We extend the hardness result to some specific edge version of the extension problem. [ABSTRACT FROM AUTHOR]

Let τ (G) and τ G (e) be the number of spanning trees of a connected graph G and the number of spanning trees of G containing edge e. The ratio d G (e) = τ G (e) / τ (G) is called the spanning tree edge density, or simply density, of e. The maximum density dep (G) = max e ∈ E (G) d G (e) is called the spanning tree edge dependence, or simply dependence, of G. In 2016, Kahl made the following two conjectures. (C1) Let p , q be positive integers, p < q. There exists some function f (p , q) such that, if G is the bipartite construction as given in Theorem 3.5 (Theorem 2.1 in the present paper), then t i ≥ f (p , q) for all 2 ≤ i ≤ n implies that dep (G) = p / q. (C2) Let p , q be positive integers, p < q. There exists a planar graph G such that dep (G) = p / q. In this paper, by using combinatorial and electrical network approaches, firstly, we show (C1) is true. Secondly, we disprove (C2) by showing that for any planar graph G , dep (G) > 1 3 . On the other hand, by construction families of planar graphs, we show that, for p / q > 1 2 , there do exist a planar graph G such that dep (G) = p / q. Furthermore, we prove that the second conjecture holds for planar multigraphs. [ABSTRACT FROM AUTHOR]

A graph G is called (k 1 , k 2) -Hamilton-connected, if for any two vertex disjoint subsets X = { x 1 , x 2 , ... , x k 1 } and U = { u 1 , u 2 , ... , u k 2 } , G contains a spanning family F of k 1 k 2 internally vertex disjoint paths such that for 1 ≤ i ≤ k 1 and 1 ≤ j ≤ k 2 , F contains an x i u j path. Let σ 2 (G) be the minimum value of deg (u) + deg (v) over all pairs { u , v } of non-adjacent vertices in G. In this paper, we prove that an n -vertex graph G is (2 , k) -Hamilton-connected if G is (5 k − 4) -connected with σ 2 (G) ≥ n + k − 2 where k ≥ 2. We also prove that if σ 2 (G) ≥ n + k 1 k 2 − 2 with k 1 , k 2 ≥ 2 , then G is (k 1 , k 2) -Hamilton-connected. Moreover, these requirements of σ 2 are tight. • This paper is motivated by k -fan connected graphs, we define (k 1 , k 2) -Hamilton-connected graphs. • This paper gives a sufficient condition for a graph to be (2 , k) -Hamilton-connected. • The results provide tight, sufficient, σ 2 (G) -conditions. • We extend the properties of Hamilton-connectedness and being k -linked. [ABSTRACT FROM AUTHOR]

The biclique B of a graph G is a maximal induced complete bipartite subgraph of G. The biclique graph K B (G) of a graph G is the graph with the bicliques of G as its vertices where two vertices of K B (G) are adjacent if and only if they have a common vertex in G. In this paper, we disprove a conjecture of Groshaus and Montero concerning Helly property of biclique graphs (Groshaus and Montero, 2021) and two conjectures of Montero concerning vertex removal in biclique graphs (Montero, 2022). In addition, we confirm a conjecture of Montero about the structural characterization of biclique graphs in the same paper. [ABSTRACT FROM AUTHOR]

Let (0 , a 1 , ... , a d − 1) n denote the function f n (x 0 , x 1 , ... , x n − 1) of degree d in n variables generated by the monomial x 0 x a 1 ⋯ x a d − 1 and having the property that f n is invariant under cyclic permutations of the variables. Such a function f n is called monomial rotation symmetric (MRS). Much of this paper extends the work on quadratic MRS functions in a 2020 paper of the authors to the case of binomial RS functions, that is sums of two quadratic MRS functions. There are also some results for the sum of any number of quadratic MRS functions. [ABSTRACT FROM AUTHOR]

El Sahili conjectured that every oriented n -path, where n ≥ 8 , is contained in every n -chromatic digraph. This conjecture was confirmed by Gallai–Hasse–Roy–Vitaver's theorem for directed paths and by Addario-Berry et al. for oriented paths with two blocks. A block of an oriented path is a maximal directed subpath. El Joubbeh showed that every (4 n − 4) -chromatic digraph contains every oriented n -path with three blocks. For oriented paths with more than three blocks, Addario-Berry et al. established that every oriented n -tree, and hence every oriented n -path with any number of blocks, is contained in every ( n 2 2 − n 2 + 1) -chromatic digraph. This paper proposes an improvement to the bound on the chromatic number for digraphs that must include all paths consisting of four blocks. In fact, we extend El Joubbeh's bound on the chromatic number from (4 n − 4) for digraphs that should contain every n -path with three blocks to (4 n − 2) for digraphs that should be contain every n -path with four blocks. This bound surpasses the one provided by Addario-Berry et al. Furthermore, we show that every oriented n -path with t blocks, t ≥ 4 , is contained in every (4 r (t) n + q (t)) -chromatic digraph where r (t) = log 2 (t − 1) and q (t) = − 20 7 8 r (t) − 1 + 6 7 . Finally, the paper highlights an improvement in the bound of Addario-Berry et al. for n -paths with t blocks, where t ≤ n − 1 2 + 1. [ABSTRACT FROM AUTHOR]

This paper studies a sliding block puzzle defined on the two by three grid, which we call the 5-puzzle. Our main aim in this paper is to show a fine geometric property of the graph representing the transitions of the positions of the 5-puzzle. We show that by identifying every position with its 180° rotation and applying path contractions, the soccer ball graph is obtained. [ABSTRACT FROM AUTHOR]

Deterministic complex networks that use iterative generation algorithms have been found to more closely mirror properties found in real world networks than the traditional uniform random graph models. In this paper we introduce a new, Iterative Independent Model (IIM), generalizing previously defined models in Bonato et al. (2020, 2009, 2017). These models use ideas from Structural Balance Theory to generate edges through a notion of cloning where "the friend of my friend is my friend" and anticloning where "the enemy of my enemy is my friend" (Bonato et al., 2020; Easley et al., 2010). In this paper, we vastly generalize these notions by allowing each vertex added at a given time step to choose independently of the other vertices if it will be cloned or anticloned. While it may seem natural to focus on a randomized model, where we randomly determine whether or not to clone any given vertex, we found the general deterministic model exhibited certain structural properties regardless of the probabilities. This allows applications to then explore the particulars, while having the theoretical model explain the structural phenomenons that occur in all possible scenarios. Throughout the paper we demonstrate that all IIM graphs have spectral gap bounded away from zero, which indicates the clustering properties also found in social networks. Furthermore, we show bounds on the diameter, domination number, and clique number further indicating the well clustered behavior of IIM graphs. Finally, for any fixed graph F all IIM graphs will eventually contain an induced copy of F. [ABSTRACT FROM AUTHOR]

Many dissemination processes in graphs can be described as follows at a basic level. At each step of the process, some vertices of the graph are coloured blue, and the remaining are coloured white, and a well-defined infection rule acts locally on a chosen element of the graph. As an outcome of this action, perhaps one or more white vertices are forced to become blue. Zero forcing, power domination and bootstrap percolation are some examples of widely studied infection rules. This paper presents a general view of infection rules on graphs, paying particular attention to monotone rules. We state several results referring to the final stable set of blue vertices at the end of the dissemination process driven by the infection rule R , and to the combinatorial transversal relation between the families of inclusion-minimal R -forcing and R -immune sets of the graph. Our results apply to many infection rules considered in the literature, as well as to new ones introduced in this paper. Besides, for each one of these infection rules, we provide a characterization of their R -immune sets formulated in terms of neighbourhood, so without referring to the iterative dissemination process acting on the graph. In the second part of the paper, and for the particular rules treated in the first part (k -PUSH, (k b , k w) -PUSH, α -PUSH, k -PULL, α -PULL, and k -wPULL), we prove the NP -Completeness of the decision problem associated to the corresponding R -immune number of the graph. [ABSTRACT FROM AUTHOR]

Let H and G be graphs. An H -colouring of G is a proper edge-colouring f : E (G) → E (H) such that for any vertex u ∈ V (G) there exists a vertex v ∈ V (H) with f ∂ G u = ∂ H v , where ∂ G u and ∂ H v respectively denote the sets of edges in G and H incident to the vertices u and v. If G admits an H -colouring we say that H colours G. The question whether there exists a graph H that colours every bridgeless cubic graph is addressed directly by the Petersen Colouring Conjecture, which states that the Petersen graph colours every bridgeless cubic graph. In 2012, Mkrtchyan showed that if this conjecture is true, the Petersen graph is the unique connected bridgeless cubic graph H which can colour all bridgeless cubic graphs. In this paper we extend this and show that if we were to remove all degree conditions on H , every bridgeless cubic graph G can be coloured substantially only by a unique other graph: the subcubic multigraph S 4 on four vertices. A few similar results are provided also under weaker assumptions on the graph G. In the second part of the paper, we also consider H -colourings of regular graphs having degree strictly greater than 3 and show that: (i) for any r > 3 , there does not exist a connected graph H (possibly containing parallel edges) that colours every r -regular multigraph, and (ii) for every r > 1 , there does not exist a connected graph H (possibly containing parallel edges) that colours every 2 r -regular simple graph. [ABSTRACT FROM AUTHOR]

The Distance Geometry Problem asks for a geometric representation of a given weighted graph in R K so that vertices are points and edges are segments with lengths equal to the corresponding weights. Two problem variants are defined by a vertex order given as part of the input, which allows the use of a branching algorithm based on K -lateration: find two possible positions for the next vertex j using the positions of K predecessors and their distances to j , then explore each position recursively, pruning positions at need. Whereas the first variant only requires the K predecessors to exist, the second variant also requires them to be contiguous and immediately preceding j. For this variant, fixed-parameter tractability of the algorithm can be established by means of a solution counting method that only depends on the graph edges (rather than their weights). Only in the first variant, however, it is possible to efficiently construct a suitable vertex order directly from the graph. Since both fixed-parameter tractability and efficient vertex order construction are desirable properties, one would need an analogous solution counting method for the first variant. In this paper we prove that such a counting method cannot be devised for the first variant. [ABSTRACT FROM AUTHOR]

In this paper, we propose two bilevel models to cope with problems concerning waste management. The first formulation stems from a multi-objective version of the problem present in the literature, while the second one improves upon the first by taking into account a theoretical result associated with the first formulation. For both models, we provide the optimistic and the pessimistic versions. We validate these formulations in a case study in the Pathum Thani province in Thailand. Moreover, we compare the results obtained by the bilevel formulation to those obtained by a multi-objective version of the problem. Finally, we provide our thoughts on future applications in this field. [ABSTRACT FROM AUTHOR]

The general position problem in graph theory asks for the largest set S of vertices of a graph G such that no shortest path of G contains more than two vertices of S. In this paper we consider a variant of the general position problem called the monophonic position problem , obtained by replacing 'shortest path' by 'induced path'. We prove some basic properties and bounds for the monophonic position number of a graph and determine the monophonic position number of some graph families, including unicyclic graphs, complements of bipartite graphs and split graphs. We show that the monophonic position number of triangle-free graphs is bounded above by the independence number. We present realisation results for the general position number, monophonic position number and monophonic hull number. Finally we discuss the complexity of the monophonic position problem. [ABSTRACT FROM AUTHOR]

We determine the sensitivity of a current optimal solution to a combinatorial optimization problem to cost changes in a set of elements. In a recent study, the concept of regular set tolerances has been introduced for a combinatorial optimization problem and for three types of cost functions, namely sum, product, and bottleneck. A regular set tolerance is the supremum amount of cost changes that can be distributed in the most favorable way to multiple elements such as not to change the current optimal solution. In this paper, we introduce an alternative concept, namely the reverse set tolerance , which is a measure of the infimum amount of cost changes to multiple elements such that the current optimal solution becomes non-optimal. We characterize the specific cases in which reverse set upper and lower tolerances have positive values and in which they are infinite. We also show a criterion for the uniqueness of an optimal solution. Furthermore, we present bounds and exact formulas for reverse set upper and lower tolerances using the relation to their corresponding single tolerance counterparts. We discuss the similarities and differences in the results between regular and reverse set tolerances. Finally, we motivate this new concept by analyzing them for special combinatorial optimization problems with important practical applications. [ABSTRACT FROM AUTHOR]

A Roman { 3 } -dominating function on a graph G is a function f : V (G) → { 0 , 1 , 2 , 3 } having the property that for any vertex u ∈ V (G) , if f (u) = 0 , then ∑ v ∈ N G (u) f (v) ≥ 3 , and if f (u) = 1 , then ∑ v ∈ N G (u) f (v) ≥ 2. The weight of a Roman { 3 } -dominating function f is the sum f (V (G)) = ∑ v ∈ V (G) f (v) and the minimum weight of a Roman { 3 } -dominating function on G is called the Roman { 3 } -domination number of G and is denoted by γ { R 3 } (G). Given a graph G , Roman { 3 } - domination asks to find the minimum weight of a Roman { 3 } -dominating function on G. In this paper, we study the algorithmic aspects of Roman { 3 } - domination on various graph classes. We show that the decision version of Roman { 3 } - domination remains NP -complete for chordal bipartite graphs, planar graphs, star-convex bipartite graphs, and chordal graphs. We show that Roman { 3 } - domination cannot be approximated within a ratio of (1 3 − ɛ) ln | V (G) | for any ɛ > 0 unless P = NP for bipartite graphs as well as chordal graphs, whereas Roman { 3 } - domination can be approximated within a factor of O (ln Δ) for graphs having maximum degree Δ. We also show that Roman { 3 } - domination is APX -complete for graphs with maximum degree 4. On the positive side, we show that Roman { 3 } - domination can be solved in linear time for chain graphs and cographs. [ABSTRACT FROM AUTHOR]

Let H = 〈 V , S 〉 be a hypergraph, where V is a set of vertices and S is a set of clusters S 1 , ... , S m , S i ⊆ V , such that the clusters in S are not necessarily disjoint. This paper considers the Clustered Spanning Tree by Paths problem, denoted by CSTP. This problem aims to decide whether a feasible solution tree exists, spanning all vertices of V , such that each cluster induces a path in the solution tree. We introduce the idea of a minimum cardinality feasible removal list and a minimum cardinality feasible insertion list, which removes or inserts vertices from or into clusters, such that using each one of the lists separately creates hypergraphs with feasible solution trees for CSTP. In addition, we decompose the intersection graph of H into smaller instances, for those cases where the intersection graph contains a cut node or a separating edge. We demonstrate how to compose a minimum cardinality feasible removal list or a minimum cardinality feasible insertion list of a given hypergraph from the smaller minimum cardinality feasible removal lists or minimum cardinality feasible insertion lists of the smaller instances. This approach may reduce the size and intricacy of the instances. [ABSTRACT FROM AUTHOR]

Assignment of one of two possible directions to every edge of an undirected graph G = (V , E) is called an orientation of G. The resulting directed graph is denoted by G ⃗. A strong orientation is one in which every vertex is reachable from every other vertex via a directed path in G ⃗. The diameter of G ⃗ , i.e., the maximum distance from any vertex to any other vertex, depends on the particular orientation. The minimum diameter among all possible orientations of G is called the oriented diameter diam ⃗ (G) of G. Let n , k be two integers such that 1 ≤ k < n. In the realm of interconnection networks of processing elements, an (n , k) -star graph S n , k offers a topology that permits to circumvent the lack of scalability of n -star graphs S n. The oriented diameter quantifies an upper limit on the delay in communication over interconnection networks. In this paper, we present a strong orientation scheme for S n , k that combines approaches suggested by Cheng and Lipman (2002) for S n , k with the one proposed by Fujita (2013) for S n , reaping benefits from both worlds. Next, we propose a distributed routing algorithm for S n , k ⃗ inspired by an algorithm proposed in Kumar et al. (2021) for S n ⃗. With the aid of both the orientation scheme and the routing algorithm, we show that diam ⃗ (S n , k) ≤ ⌊ n + k 2 ⌋ + 2 k + 6 − δ (n , k) where δ (n , k) is a non-negative function. The function δ (n , k) takes on values 2 k − n , 0 , and n − 3 k 2 respectively for three disjoint intervals k > n 2 , n 3 < k ≤ n 2 and k ≤ n 3 . For every value of n , k , our upper bound performs better than all known bounds in literature. [ABSTRACT FROM AUTHOR]

In the path version of the Travelling Salesman Problem (Path-TSP), a salesman is looking for the shortest Hamiltonian path through a set of n cities. The salesman has to start his journey at a given city s , visit every city exactly once, and finally end his trip at another given city t. In this paper we show that a special case of the Path-TSP with a Demidenko distance matrix is solvable in polynomial time. Demidenko distance matrices fulfill a particular condition abstracted from the convex Euclidian special case by Demidenko (1979) as an extension of an earlier work of Kalmanson (1975). We identify a number of crucial combinatorial properties of the optimal solution and design a dynamic programming approach with time complexity O (n 6). [ABSTRACT FROM AUTHOR]

The k -matching preclusion number of a graph is the minimum number of edges whose deletion results in the remaining graph that has neither perfect k -matchings nor almost perfect k -matchings. For many networks, their optimal k -matching preclusion sets are precisely those edges incident with a single vertex. In this paper, we introduce the concept of conditional k -matching preclusion, in which isolated vertices are not permitted in fault networks. We establish the conditional k -matching preclusion numbers and all possible minimum conditional k -matching preclusion sets for n -dimensional torus networks with n ≥ 3. In addition, we investigate the relationship between all optimal sets for three kinds of (conditional) matching preclusion problems. [ABSTRACT FROM AUTHOR]

The proximity π = π (G) of a connected graph G is the minimum, over all vertices, of the average distance from a vertex to all others. Similarly, the maximum is called the remoteness and denoted by ρ = ρ (G). The concepts of proximity and remoteness, first defined in 2006, attracted the attention of several researchers in Graph Theory. Their investigation led to a considerable number of publications. In this paper we present a survey of the research work done to date. [ABSTRACT FROM AUTHOR]

A graph is claw-free if it does not contain a star of order 4 as an induced subgraph. In this paper, we characterize all claw-free connected graphs with all but four eigenvalues equal to 0 or − 1. [ABSTRACT FROM AUTHOR]

Upgrading the connections of an existing network is common practice in telecommunication and electric grid networks. In most applications such as low-voltage grids, upgrading is preferable compared to building a new network from scratch given the limited resources available. When the structure of the underlying network is required to be a tree, this leads to a novel variant of the Constrained Bottleneck Spanning Tree Problem (CBST) that takes into account edge weight variability. There are only two existing polynomial-time algorithms that can tackle this problem after transforming the network into a CBST instance in linear time. Through a computational study, we highlight the strengths and weaknesses of these approaches. By combining the strengths of these algorithms, namely progressive network reduction and iterative bound alteration, we developed a polynomial-time algorithm that outperforms both existing algorithms in terms of computation speed. Beyond solving the practical problem at hand, this paper lays the foundations for future research into what we term the Constrained Bottleneck Spanning Tree Problem with Upgrades (CBSTU). [ABSTRACT FROM AUTHOR]

The square of a graph G , denoted by G 2 , is obtained from G by adding an edge to connect every pair of vertices with a common neighbor in G. In this paper we prove that for every planar graph G with maximum degree at most 5, G 2 admits a proper vertex coloring using at most 17 colors, which improves the upper bound 18 recently obtained by Hou et al. (2023). [ABSTRACT FROM AUTHOR]

The general position problem for graphs was inspired by the no-three-in-line problem from discrete geometry. A set S of vertices of a graph G is a general position set if no shortest path in G contains three or more vertices of S. The general position number of G is the number of vertices in a largest general position set. In this paper we investigate the general position numbers of the Mycielskian of graphs. We give tight upper and lower bounds on the general position number of the Mycielskian of a graph G and investigate the structure of the graphs meeting these bounds. We determine this number exactly for common classes of graphs, including cubic graphs and a wide range of trees. [ABSTRACT FROM AUTHOR]

The spectral spread of the eccentricity matrix E (G) of a graph G is defined as the difference between the largest and the smallest eigenvalue of E (G). While the trace norm of the eccentricity matrix is the absolute sum of the eigenvalues of E (G). In this paper, we obtain various bounds for the spread in terms of the various parameters of G and related it with the trace norm of E (G). We characterize some extremal graphs attaining such bounds. [ABSTRACT FROM AUTHOR]

One of the most interesting open problems of a digraph is Seymour's Second Neighborhood Conjecture (SSNC), which asserts that every digraph D has a vertex v satisfying d + + (v) ≥ d + (v) , we called such vertex v a Seymour vertex. Sullivan stated two compromise conjectures on SSNC. Let v ∈ V (D) if d + + (v) ≥ d − (v) , then v is called a Sullivan-1 vertex. If d + + (v) + d + (v) ≥ 2 d − (v) , then v is called a Sullivan-2 vertex. In this paper, we give a condition that the digraph has n Seymour vertices. And we also prove that every random tournament T n has n Sullivan-1 vertices and at least n 2 − n log n Sullivan-2 vertices with high probability. [ABSTRACT FROM AUTHOR]

Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic traceability, and in this paper, we study the class of bounded clique-width graphs through the lens of succinct data structures. A data structure is said to be succinct if the amount of space used by the data structure is information-theoretically optimal up to lower-order additive terms. More specifically, we design a succinct data structure for graphs on n vertices whose clique-width is at most k ≤ ϵ log n for some constant 0 < ϵ < 1 / 6 , that supports degree, adjacency, and neighborhood queries efficiently. This resolves an open problem of Kamali (Algorithmica-2018). As an application of our main technique, we also propose succinct data structures for distance-hereditary and Ptolemaic graphs, which are subclasses of the class of graphs with clique-width at most 3. [ABSTRACT FROM AUTHOR]

The domination game is played on a graph G by two players, Dominator and Staller, who alternate in selecting vertices until each vertex in the graph G is contained in the closed neighbourhood of the set of selected vertices. Dominator's aim is to reach this state in as few moves as possible, whereas Staller wants the game to last as long as possible. In this paper, we prove that if G has n vertices and minimum degree at least 2, then Dominator has a strategy to finish the domination game on G within 10 n / 17 + 1 / 17 moves, thus making progress towards a conjecture by Bujtás, Iršič and Klavžar. [ABSTRACT FROM AUTHOR]

Cyclic vertex connectivity c κ and cyclic edge connectivity c λ are two important kinds of conditional connectivity, which reflect the number of vertices or edges that can be removed before the graph is disconnected and at least two components contain a cycle, respectively. They have important applications in various networks such as computer networks or biochemical networks. In addition, a fullerene is a special kind of molecule in chemistry. A classic fullerene graph is a 3-connected cubic planar graph with only pentagonal and hexagonal faces. (4, 5, 6)-fullerene graphs are atypical fullerene graphs which also contain 4-faces. In this paper, we prove that c κ = c λ for (4 , 5 , 6) -fullerene graphs except for four exceptional graphs with order less than 16. We also give O (ν) -algorithms to determine the cyclic vertex connectivity and the cyclic edge connectivity of (4 , 5 , 6) -fullerene graphs. [ABSTRACT FROM AUTHOR]

For a vertex v of a graph, the local complementation at v is an operation that replaces the neighborhood of v by its complement graph. Two graphs are locally equivalent if one is obtained from the other by a sequence of local complementations. A graph H is a vertex-minor of a graph G if H is an induced subgraph of a graph locally equivalent to G. Although this concept was introduced in the 1980s, it was not widely known and except for the survey paper of Bouchet published in 1990, there is no comprehensive survey listing all the new developments. We survey classic and recent theorems and conjectures on vertex-minors and related concepts such as circle graphs, cut-rank functions, rank-width, and interlace polynomials. [ABSTRACT FROM AUTHOR]

A total dominating set in a graph G is a set S of vertices of G such that every vertex in G is adjacent to a vertex in S. Recently, the following question was proposed: "Is it true that every connected cubic graph containing a 3-cycle has two vertex disjoint total dominating sets?" In this paper, we give a negative answer to this question. Moreover, we prove that if we replace 3-cycle with 4-cycle the answer is affirmative. This implies every connected cubic graph containing a diamond (the complete graph of order 4 minus one edge) as a subgraph can be partitioned into two total dominating sets, a result that was proved in 2017. [ABSTRACT FROM AUTHOR]

For integer k ≥ 2 , a graph G is called k -leaf-connected if | V (G) | ≥ k + 1 and given any subset S ⊆ V (G) with | S | = k , G always has a spanning tree T such that S is precisely the set of leaves of T. Thus a graph is 2-leaf-connected if and only if it is Hamiltonian-connected. The first Zagreb index M 1 (G) is equal to the sum of squares of the degrees of the vertices of the underlying molecular graph G. The reciprocal degree distance (RDD), defined as vertex-degree-weighted sum of the reciprocal distances, that is, RDD (G) = ∑ v i ≠ v j deg G (v i) + deg G (v j) d G (v i , v j) , where deg G (v i) is the degree of the vertex v i in G and d G (v i , v j) denotes the distance between two vertices v i and v j in G. The forgotten topological index of G is the sum of cubes of all its vertex degrees, which plays a significant role in measuring the branching of the carbon atom skeleton. Finding sufficient conditions for graphs possessing certain properties is an important and meaningful problem. In this paper, we give sufficient conditions in terms of the first Zagreb index, the reciprocal degree distance or the forgotten topological index for a graph to be k -leaf-connected, which generalizes two results of An (2022). All of these results are best possible. • A sharp bound on the first Zagreb index that ensures k-leaf-connected is given. • A sharp bound on reciprocal degree distance that ensures k-leaf-connected is given. • A sharp bound on the forgotten topological index that ensures k-leaf-connected is given. [ABSTRACT FROM AUTHOR]

Four Color Theorem implies that the independence number of every planar graph is at least n / 4. A cactus graph is a connected planar graph whose block is either an edge or a cycle. In this paper, the lower bound for independence number of cactus graphs is improved to ⌈ n / 3 ⌉. Moreover, the maximum spectral radius of cactus graphs with fixed independence number is determined. [ABSTRACT FROM AUTHOR]

The classical Shapley value for cooperative games determines a payoff vector considering that the formation of the grand coalition is made by incorporating players one by one. Later, this method was generalized for games with restricted cooperation by several known mathematical structures: partitions, graphs, convex geometries, antimatroids, matroids or simplicial complexes. In this paper we consider games over simplicial complex with an extra information about the relationships of the agents, a filtration of the complex. Filtrations are very known simplicial structures in the social and neuronal networks. We propose a Shapley value for these situations and an axiomatization. [ABSTRACT FROM AUTHOR]