Search

Robertson and Seymour proved that the family of all graphs containing a fixed graph H as a minor has the Erdős-Posa property if and only if H is planar. We show that this is no longer true for the edge version of the Erdős-Posa property, and indeed even fails when H is an arbitrary subcubic tree of large pathwidth or a long ladder. This answers a question of Raymond, Sau and Thilikos.

Suppose that we are given an independent set \(I_0\) of a graph G, and an integer \(l\ge 0\). Then, we are asked to find an independent set of G having the maximum size among independent sets that are reachable from \(I_0\) by either adding or removing a single vertex at a time such that all intermediate independent sets are of size at least \(l\). We show that this problem is PSPACE-hard even for bounded pathwidth graphs, and remains NP-hard for planar graphs. On the other hand, we give a linear-time algorithm to solve the problem for chordal graphs. We also study the parameterized complexity of the problem with respect to the following three parameters: the degeneracy \(d\) of an input graph, a lower bound \(l\) on the size of independent sets, and a lower bound \(s\) on the size of a solution reachable from \(I_0\). We show that the problem is fixed-parameter intractable when only one of \(d\), \(l\), and \(s\) is taken as a parameter. On the other hand, we give a fixed-parameter algorithm when parameterized by \(s+d\); this result implies that the problem parameterized only by \(s\) is fixed-parameter tractable for planar graphs, and for bounded treewidth graphs.

International audience; The node search game against a lazy (or, respectively, agile) invisible robber has been introduced as a search-game analogue of the treewidth parameter (and, respectively, pathwidth). In the \emph{connected} variants of the above two games, we additionally demand that, at each moment of the search, the \emph{clean} territories are {\sl connected}. The connected search game against an agile and invisible robberhas been extensively examined. The monotone variant (where we also demand that the clean territories are progressively increasing) of this game, corresponds to the graph parameter of {\sl connected pathwidth}. It is known that \emph{the price of connectivtiy} to search for an agile robber is bounded by $2$, that is the connected pathwidth of a graph is at most twice (plus some constant) its pathwidth.In this paper, we investigate the study of the connected search game against a {\sl lazy} robber. A lazy robber moves only when the searchers' strategy threatens the location that he currently occupies. We introduce two alternative graph-theoretical formulations of this game, one in terms of connected tree decompositions, and one in terms of (connected) layouts, leading to the graph parameter of {\sl connected treewidth}. We observe that connected treewidth parameter is closed under contractions and prove that for every $k\geq 2$, the set of contraction obstructions of the class of graphs with connected treewidth at most $k$ is infinite.Our main result is a complete characterisation of the obstruction set for $k=2$. One may observe that, so far, only a few complete obstruction sets are explicity known for contraction closed graph classes.We finally show that, in contrast to the agile robber game, the price of connectivity is unbounded.

A graph $G$ is a prime distance graph (respectively, a 2-odd graph) if its vertices can be labeled with distinct integers such that for any two adjacent vertices, the difference of their labels is prime (either 2 or odd). We prove that trees, cycles, and bipartite graphs are prime distance graphs, and that Dutch windmill graphs and paper mill graphs are prime distance graphs if and only if the Twin Prime Conjecture and dePolignac's Conjecture are true, respectively. We give a characterization of 2-odd graphs in terms of edge colorings, and we use this characterization to determine which circulant graphs of the form $Circ(n, \{1,k\})$ are 2-odd and to prove results on circulant prime distance graphs.

The topological theory for semi-complete digraphs, pioneered by Chudnovsky, Fradkin, Kim, Scott, and Seymour [10] , [11] , [12] , [28] , [43] , [39] , concentrates on the interplay between the most important width measures — cutwidth and pathwidth — and containment relations like topological/minor containment or immersion. We propose a new approach to this theory that is based on outdegree orderings and new families of obstacles for cutwidth and pathwidth. Using the new approach we are able to reprove the most important known results in a unified and simplified manner, as well as provide multiple improvements. Notably, we obtain a number of efficient approximation and fixed-parameter tractable algorithms for computing width measures of semi-complete digraphs, as well as fast fixed-parameter tractable algorithms for testing containment relations in the semi-complete setting. As a direct corollary of our work, we also derive explicit and essentially tight bounds on duality relations between width parameters and containment orderings in semi-complete digraphs.

A graph is called P t -free if it does not contain the path on t vertices as an induced subgraph. Let H be a multigraph with the property that any two distinct vertices share at most one common neighbour. We show that the generating function for (list) graph homomorphisms from G to H can be calculated in subexponential time 2 O t n log ( n ) for n = | V ( G ) | in the class of P t -free graphs G . As a corollary, we show that the number of 3-colourings of a P t -free graph G can be found in subexponential time. On the other hand, no subexponential time algorithm exists for 4-colourability of P t -free graphs assuming the Exponential Time Hypothesis. Along the way, we prove that P t -free graphs have pathwidth that is linear in their maximum degree.

Half graphs and their variants, such as ladders, semi-ladders and co-matchings, are combinatorial objects that encode total orders in graphs. Works by Adler and Adler (Eur. J. Comb.; 2014) and Fabia\'nski et al. (STACS; 2019) prove that in the powers of sparse graphs, one cannot find arbitrarily large objects of this kind. However, these proofs either are non-constructive, or provide only loose upper bounds on the orders of half graphs and semi-ladders. In this work we provide nearly tight asymptotic lower and upper bounds on the maximum order of half graphs, parameterized on the distance, in the following classes of sparse graphs: planar graphs, graphs with bounded maximum degree, graphs with bounded pathwidth or treewidth, and graphs excluding a fixed clique as a minor. The most significant part of our work is the upper bound for planar graphs. Here, we employ techniques of structural graph theory to analyze semi-ladders in planar graphs through the notion of cages, which expose a topological structure in semi-ladders. As an essential building block of this proof, we also state and prove a new structural result, yielding a fully polynomial bound on the neighborhood complexity in the class of planar graphs., Comment: 83 pages, 32 figures

International audience; In the Weighted Total Acquisition problem (WTA) on a weighted graph $G$ (only positive non-zero weights), a vertex $v$ can acquire the total weight of a neighbour $u$ if and only if the current weight of $v$ is at least that of $u$. The new weight of $u$ is then zero, and the new weight of $v$ is then the sum of the weights at $u$ and $v$ just before the acquisition. Over all possible acquisition sequences in $G$ with weight function $w$, the minimum number of vertices with a non-zero weight at the end is denoted by $a_t(G,w)$. Given a graph $G$, a weighting $w$, and an integer $k\geq 1$, the WTA problem asks whether $a_t(G,w)\leq k$. The Binary (Unary resp.) WTA problem corresponds to the WTA problem when the weights are encoded in binary (unary resp.).We prove that Unary WTA is polynomial-time solvable in graphs of bounded treewidth and degree. When only the treewidth is bounded, this algorithm is quasi-polynomial, i.e., it runs in time $W^{O(\log W)}$, where $W$ is the sum of the weights of the vertices. Moreover, we show that Unary WTA is FPT in trees when parameterized by the maximum degree. On the negative side, we show that WTA is NP-complete in trivially perfect graphs and split graphs, even when $k=1$ in the latter.We prove that the Binary WTA problem is NP-complete in trees of bounded degree, trees of bounded depth, and wheels, but that it is in XP for trees and wheels when parameterized by the solution size. Moreover, we show that Binary WTA is NP-complete in $K_{3,n}$, planar graphs of pathwidth 2, and unit interval graphs even when $k=1$, and in trivially perfect graphs when $k\geq 2$ (but polynomial-time solvable when $k=1$).

This paper proves that the existence of a feasible schedule for a set of dependent tasks of unit execution times with release dates and deadlines on a limited number of processors is a fixed-parameter tractable problem. The parameter considered is the pathwidth of the interval graph associated with the time windows of the tasks. A fixed-parameter algorithm based on a dynamic programming approach is developed and proved to solve this decision problem. Fixed-parameter algorithms for the two classical problems P | p r e c , p i = 1 , r i | C max and P | p r e c , p i = 1 , r i | L max are then derived using a binary search. They are, as far as we know, the first fixed-parameter algorithms for these scheduling problems.

We prove the conjecture of Seymour (1993) that for every apex-forest $H_1$ and outerplanar graph $H_2$ there is an integer $p$ such that every 2-connected graph of pathwidth at least $p$ contains $H_1$ or $H_2$ as a minor. An independent proof was recently obtained by Dang and Thomas., Comment: v4: Small changes suggested by a referee

A graph $G$ is said to be the intersection of graphs $G_1,G_2,\ldots,G_k$ if $V(G)=V(G_1)=V(G_2)=\cdots=V(G_k)$ and $E(G)=E(G_1)\cap E(G_2)\cap\cdots\cap E(G_k)$. For a graph $G$, $\mathrm{dim}_{COG}(G)$ (resp. $\mathrm{dim}_{TH}(G)$) denotes the minimum number of cographs (resp. threshold graphs) whose intersection gives $G$. We present several new bounds on these parameters for general graphs as well as some special classes of graphs. It is shown that for any graph $G$: (a) $\mathrm{dim}_{COG}(G)\leq\mathrm{tw}(G)+2$, (b) $\mathrm{dim}_{TH}(G)\leq\mathrm{pw}(G)+1$, and (c) $\mathrm{dim}_{TH}(G)\leq\chi(G)\cdot\mathrm{box}(G)$, where $\mathrm{tw}(G)$, $\mathrm{pw}(G)$, $\chi(G)$ and $\mathrm{box}(G)$ denote respectively the treewidth, pathwidth, chromatic number and boxicity of the graph $G$. We also derive the exact values for these parameters for cycles and show that every forest is the intersection of two cographs. These results allow us to derive improved bounds on $\mathrm{dim}_{COG}(G)$ and $\mathrm{dim}_{TH}(G)$ when $G$ belongs to some special graph classes., Comment: 14 pages, 4 figures, accepted for the conference CALDAM 2020

A graph G is said to be 1 -perfectly orientable if it has an orientation D such that for every vertex v ∈ V ( G ) , the out-neighborhood of v in D is a clique in G . In 1982 , Skrien posed the problem of characterizing the class of 1 -perfectly orientable graphs. This graph class forms a common generalization of the classes of chordal and circular arc graphs; however, while polynomially recognizable via a reduction to 2 -SAT, no structural characterization of this intriguing class of graphs is known. Based on a reduction of the study of 1 -perfectly orientable graphs to the biconnected case, we characterize, both in terms of forbidden induced minors and in terms of composition theorems, the classes of 1 -perfectly orientable K 4 -minor-free graphs and of 1 -perfectly orientable outerplanar graphs. As part of our approach, we introduce a class of graphs defined similarly as the class of 2 -trees and relate the classes of graphs under consideration to two other graph classes closed under induced minors studied in the literature: cyclically orientable graphs and graphs of separability at most 2 .

A graph H is a square root of a graph G if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The Square Root problem is that of deciding whether a given graph admits a square root. This problem is known to be NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed graph classes and a very limited number of other graph classes. We prove that Square Root is O(n)-time solvable for graphs of maximum degree 5 and O(n4)-time solvable for graphs of maximum degree at most 6.

We consider the task to compute the pathwidth of a graph which is known to be equivalent to solving the vertex separation problem. The latter is naturally modeled as a linear ordering problem with respect to the vertices of the graph. Present mixed-integer programs for the vertex separation problem express linear orders using either position or set assignment variables. However, as we show, the lower bound on the pathwidth obtained when solving their linear programming relaxations is zero for any directed graph. This is one reason for their limited utility in solving larger instances to optimality. We then present a new formulation that is based on conventional linear ordering variables and a slightly different perspective on the problem. Its relaxation provably delivers non-zero lower bounds for any graph whose pathwidth is non-zero. Further structural results for and extensions to this formulation are discussed. Finally, an experimental evaluation of three mixed-integer programs, each representing one of the different yet existing modeling approaches, displays their potentials and limitations when used to solve the problem to optimality in practice.

Chordal graphs, permutation graphs, and interval graphs are among many classes of graphs which can be characterized by the existence of certain acyclic orientations and vertex orderings. These types of characterizations exist for some of their bipartite analogues such as chordal bipartite graphs and bipartite permutation graphs. Chvatal proved that a bipartite graph G is chordal bipartite if and only if the complement G ¯ of G has a vertex ordering ≺ such that for every induced path a b c d in G ¯ , a ≺ b implies c ≺ d . Recently, Le proved that a bipartite graph G is a permutation graph if and only if G ¯ admits an acyclic orientation such that for every induced path a b c d in G ¯ , a b is an oriented edge if and only if c d is. Interestingly these orientation and vertex ordering characterizations are stated on the complements of bipartite graphs. We show that interval bigraphs and interval containment bigraphs also admit similar characterizations in terms of vertex orderings and acyclic orientations of their complements.

A vertex of a connected graph is a contour vertex provided the eccentricity of the vertex is at least as large as that of each of its neighbors. We consider the question of whether the set S of contour vertices of a connected graph is geodetic, i.e., whether every vertex of the graph lies on a shortest path (geodesic) between some pair of vertices in S . In general, it is known that when long induced cycles are forbidden (for chordal graphs) the answer is in the affirmative, but otherwise (even for weakly chordal graphs) the answer is in the negative. For bipartite graphs, it is known that when long induced cycles are allowed, the answer is in the negative. In contrast, we show that when long induced cycles are forbidden in bipartite graphs, namely for chordal bipartite graphs, the answer is in the affirmative. Our result also shows that while the answer is in the negative for bipartite graphs and weakly chordal graphs, for a graph that is both bipartite and weakly chordal, the answer is in the affirmative.

Several well-studied classes of graphs admit structural characterizations via proper 2-cutsets which lead to polynomial-time recognition algorithms. The algorithms so far obtained for those recognition problems do not guarantee linear-time complexity. The bottleneck to those algorithms is the Ω ( n m ) -time complexity to fully decompose by proper 2-cutsets a graph with n vertices and m edges. In the present work, we investigate the 3-connected components of a graph and propose the use of the SPQR-tree data structure to obtain a fully decomposed graph in linear time. As a consequence, we show that the recognition of chordless graphs and of graphs that do not contain a propeller as a subgraph can be done in linear time, answering questions in the existing literature.

Let F , G , and H be simple graphs. We write F → ( G , H ) to mean that any red–blue coloring of all edges of F will contain either a red copy of G or a blue copy of H . A graph F (without isolated vertices) satisfying F → ( G , H ) and for each e ∈ E ( F ) , ( F − e ) ↛ ( G , H ) is called a Ramsey ( G , H ) -minimal graph. The set of all Ramsey ( G , H ) -minimal graphs is denoted by ℛ ( G , H ) . In this paper, we derive the necessary and sufficient condition of graphs belonging to ℛ ( 4 K 2 , H ) , for any connected graph H . Moreover, we give a relation between Ramsey ( 4 K 2 , P 3 ) - and ( 3 K 2 , P 3 ) -minimal graphs, and Ramsey ( 4 K 2 , P 3 ) - and ( 2 K 2 , P 3 ) -minimal graphs. Furthermore, we determine all graphs in ℛ ( 4 K 2 , P 3 ) .

We study those unit interval graphs having a model with intervals of integer endpoints and prescribed length. We present a structural result for this graph subclass which leads to a quadratic-time recognition algorithm, giving as positive certificate a model of minimum total length and as negative certificate a forbidden induced subgraph. We also present a quadratic-time algorithm to build, given a unit interval graph, a unit interval model with integer endpoints for which the interval length is as minimum as possible. Fil: Duran, Guillermo Alfredo. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad de Chile; Chile. Universidad de Buenos Aires; Argentina Fil: Fernández Slezak, F.. Universidad de Buenos Aires; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Grippo, L.N.. Universidad Nacional de General Sarmiento; Argentina Fil: Oliveira, F.de S.. Universidade do Estado de Rio do Janeiro; Brasil Fil: Szwarcfiter, Jayme L.. Universidade do Estado de Rio do Janeiro; Brasil. Universidade Federal do Rio de Janeiro; Brasil

In this work we investigate the chordality of squares and line graph squares of graphs. We prove a sufficient condition for the chordality of squares of graphs not containing induced cycles of length at least five. Moreover, we characterize the chordality of graph squares by forbidden subgraphs. Transferring that result to line graphs allows us to characterize the chordality of line graph squares.

The vertices of a graph are classified into seven types by J.T. Hedetniemi, S.M. Hedetniemi, S.T. Hedetniemi and T.M. Lewis and they ask the following questions: (1) What is the smallest order n of a graph having $$n-2$$ very typical vertices or $$n-2$$ typical vertices? (2) What is the smallest order of a pantypical graph? We answer these two questions and determine all the possible orders of the graphs in these three classes in this paper.

A simple undirected graph G has the me2-property if every pair of distinct vertices of G is connected by a path of length 2, but this property does not survive the deletion of an edge. This article considers graphs that can be embedded as induced subgraphs of me2-graphs by the introduction of additional mutually non-adjacent vertices and suitably chosen edges. The main results concern such embeddings of trees.

A graph G is called uniquely k -list colorable (UkLC) if there exists a list of colors on its vertices, say $$L=\lbrace S_v \mid v \in V(G) \rbrace $$ , each of size k, such that there is a unique proper list coloring of G from this list of colors. A graph G is said to have property M(k) if it is not uniquely k-list colorable. Mahmoodian and Mahdian (Ars Comb 51:295–305, 1999) characterized all graphs with property M(2). For $$k\ge 3$$ property M(k) has been studied only for multipartite graphs. Here we find bounds on M(k) for graphs embedded on surfaces, and obtain new results on planar graphs. We begin a general study of bounds on M(k) for regular graphs, as well as for graphs with varying list sizes.

In Knor et al. (2016) authors conjectured that for a graph G , W min ( G ) is achieved for a χ ( G ) -coloring-induced orientation. They also proved the conjecture holds for bipartite graphs, complete graphs, prisms and Petersen graph. However, we find that there exists a graph G such that any minimum Wiener index orientation of G is not χ ( G ) -coloring-induced. This means the conjecture does not hold in general. Furthermore, we explore some graphs which do not satisfy the conjecture.

One of the most famous algorithmic meta-theorems states that every graph property which can be defined in counting monadic second order logic (CMSOL) can be checked in linear time on graphs of bounded treewidth, which is known as Courcelle’s Theorem (Courcelle, 1990). These algorithms are constructed as finite state tree automata and hence every CMSOL-definable graph property is recognizable. Courcelle also conjectured that the converse holds, i.e. every recognizable graph property is definable in CMSOL for graphs of bounded treewidth. In this paper we prove two special cases of this conjecture, first for the class of k -outerplanar graphs, which are known to have treewidth at most 3 k − 1 (Bodlaender, 1998) and for graphs of bounded treewidth without chordless cycles of length at least some constant l . We furthermore show that for a proof of Courcelle’s Conjecture it is sufficient to show that all members of a graph class admit constant width tree decompositions whose bags and edges can be identified with MSOL-predicates. For graph classes that admit MSOL-definable constant width tree decompositions that have bounded degree or allow for a linear ordering of all nodes with the same parent we even give a stronger result: In that case, the counting predicates of CMSOL are not needed.

In this article, a technique to construct cyclic orthogonal double covers (CODCs) of regular circulant graphs by certain infinite graph classes such as complete bipartite and tripartite graphs and disjoint union of butterfly and K 1 , 2 n − 10 is introduced.

In this paper, we derive bounds on the optimal average information ratio of the access structures based on general graphs and investigate the value of the ratio for unicycle graphs and some bipartite graphs. We determine the exact values of this ratio for some infinite classes of bipartite graphs and unicycle graphs. This extends previous results. We also provide good bounds on the optimal average information ratio for all unicycle graphs.

A C k -free 2 -matching in an undirected graph is a simple 2 -matching which does not contain cycles of length k or less. The complexity of finding the maximum C k -free 2 -matching in a given graph varies depending on k and the type of input graph. The case where k = 4 and the graph is bipartite, which is called the maximum square-free 2 -matching problem in bipartite graphs, is well-solved. Previous results for this special case include min-max theorems, polynomial combinatorial algorithms, a linear programming formulation with dual integrality for a weighted version, and discrete convex structures. In this paper, we further investigate the structure of square-free 2 -matchings in bipartite graphs and present new decomposition theorems. These theorems serve as analogues of the Dulmage-Mendelsohn decomposition for matchings in bipartite graphs and the Edmonds-Gallai decomposition for matchings in nonbipartite graphs. We exhibit two canonical minimizers for the set function in the min-max formula, and a characterization of the maximum square-free 2 -matchings with the aid of these canonical minimizers.

A weighted (unweighted) graph G is called equiarboreal if the sum of weights (the number) of spanning trees containing a given edge in G is independent of the choice of edge. In this paper, we give some resistance characterizations of equiarboreal weighted and unweighted graphs, and obtain the necessary and sufficient conditions for k -subdivision graphs, iterated double graphs, line graphs of regular graphs and duals of planar graphs to be equiarboreal. Applying these results, we obtain new infinite families of equiarboreal graphs, including iterated double graphs of 1-walk-regular graphs, line graphs of triangle-free 2-walk-regular graphs, and duals of equiarboreal planar graphs.

For a (simple) graph G, we denote by | V ( G ) | , | E ( G ) | , η ( G ) and m ( G ) respectively the order, the number of edges, the nullity, and the matching number of G. It was shown by Wang and Wong (2014) that for every graph G, | V ( G ) | − 2 m ( G ) − c ( G ) ≤ η ( G ) ≤ | V ( G ) | − 2 m ( G ) + 2 c ( G ) , where c ( G ) : = | E ( G ) | − | V ( G ) | + θ ( G ) is the cyclomatic number of G, θ ( G ) being the number of components of G. Graphs with the maximal nullity condition have been characterized by Song et al. (2015), and graphs with the minimal nullity condition have also been characterized independently by Rula et al. (2016) and Wang (2016). Earlier Guo et al. (2009) had also shown that for a unicyclic graph G, η ( G ) − | V ( G ) | + 2 m ( G ) can take only one of the values − 1 , 0 or 2, and they characterized these three types of unicyclic graphs. In this paper, exploiting the concepts of canonical star associated with a rooted tree, the canonical unicyclic graph associated with a unicyclic graph and a crucial subgraph of a graph, we correct, complete and extend the work of previous authors on this topic. We give a nontrivial proof for the fact that the crucial subgraphs of a graph, as introduced by Wang (2016), are unique up to isomorphism. More complete lists of characterizations for the three types of unicyclic graphs, for nonsingular unicyclic graphs, and for graphs with the minimal or maximal nullity conditions are found. It is proved that if c , n are given positive integers with n ≥ 6 c + 2 , then for any integer k , − c ≤ k ≤ 2 c , k ≠ 2 c − 1 , there exists a connected graph G of order n that satisfies c ( G ) = c and η ( G ) − | V ( G ) | + 2 m ( G ) = k ; however, if k is replaced by 2 c − 1 then there is no graph G of any order that satisfies the corresponding conditions.

For a graph Γ the algebraic connectivity denoted by a ( Γ ) , is the second smallest eigenvalue of the Laplacian matrix of Γ . In Jiang et al. (2015), proved a unique graph with first minimum algebraic connectivity among the graphs which belong to a class of graphs whose complements are trees. In this paper, we characterize the unique graph with second minimum algebraic connectivity in the same aforesaid class of graphs.

This paper deals with the subject of minimal path decomposition of complete bipartite graphs. A path decomposition of a graph is a decomposition of it into simple paths such that every edge appears in exactly one path. If the number of paths is the minimum possible, the path decomposition is called minimal. Algorithms that derive such decompositions are presented, along with their proof of correctness, for the three out of the four possible cases of a complete bipartite graph. 35 3 684 702

Gallai conjectured (1966) that the edge-set of a simple graph G with n vertices can be covered by at most ( n + 1 ) / 2 edge-disjoint paths. Lovasz [Lovasz, L., On covering of graphs, in: Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968 pp. 231–236.] verified this conjecture for graphs with at most one vertex of even degree, and Pyber [Pyber, L., Covering the edges of a connected graph by paths, J. Combin. Theory Ser. B 66 (1996), pp. 152–159.] verified it for graphs in which every cycle contains a vertex of odd degree. Recently, Bonamy and Perrett verified this Conjecture for graphs with maximum degree at most 5. In this paper, we verify the Conjecture for graphs with treewidth at most 3.

Given an underlying undirected simple graph, we consider the set of its acyclic orientations. Each of these orientations induces a partial order on the vertices of our graph and, therefore, we can count the number of linear extensions of these posets. We want to know which choice of orientation maximizes the number of linear extensions of the corresponding poset, and this problem will be solved essentially for comparability graphs and odd cycles, presenting several proofs. The corresponding enumeration problem for arbitrary simple graphs will be studied, including the case of random graphs; this will culminate in (1) new bounds for the volume of the stable set polytope and (2) strong concentration results for our enumerative statistic and for the graph entropy, which hold true a.s. for random graphs. We will then argue that our problem springs up naturally in the theory of graphical arrangements and graphical zonotopes.

A non-planar graph G is almost-planar if, for every edge e of G, either G \ e or G/e is planar. We provide an algorithmic proof of a theorem by D. K. Wagner, according to which every almost-planar graph can be reduced to the graph K 3 , 3 by some sequence of series/parallel reductions and delta-wye exchanges such that the reduction sequence is formed by almost-planar graphs. We study 3-connected almost-planar graphs on the projective plane and establish duality relations between the resulting families. We show that one family reduces to K 3 , 3 (with an added parallel edge) while the dual family reduces to K5. We also characterize 3-terminal delta-wye reducibility for almost-planar graphs.

The biclique graph KB(G) is the intersection graph of bicliques of a graph G. The aim of our work is to recognize graphs that are biclique graphs of bipartite permutation graphs. In this paper we prove that the biclique graph of a bipartite permutation graph is a K1,4-free interval graph, and we present a characterization of such graphs and a characterization of a subclass that leads to a polynomial time recognition algorithm.

In 1965, Jack Edmonds proposed his celebrated polynomial-time algorithm to find a maximum matching in a graph. It is well-known that finding a maximum matching in G is equivalent to finding a maximum independent set in the line graph of G . For general graphs, the maximum independent set problem is NP-hard. What makes this problem easy in the class of line graphs and what other restrictions can lead to an efficient solution of the problem? In the present paper, we analyse these and related questions. We also review various techniques that may lead to efficient algorithms for the maximum independent set problem in restricted graph families, with a focus given to augmenting graphs and graph transformations. Both techniques have been used in the solution of Edmonds to the maximum matching problem, i.e. in the solution to the maximum independent set problem in the class of line graphs. We survey various results that exploit these techniques beyond the line graphs.

In this paper we characterize distance-regular graphs with diameter three having exactly three distinct distance eigenvalues, and also bipartite distance-regular graphs with diameter four having three distinct distance eigenvalues. We derive some properties and give particular examples of such graphs. We also present an infinite family of bipartite semiregular graphs with diameter four having exactly four distinct distance eigenvalues. With these results, we address some problems posed in Atik and Panigrahi (2015) [3] .

Based on electrically equivalent transformations on weighted graphs, in this paper, we present a formula for computing the number of spanning trees of a family of 2-separable graphs formed from two base graphs by 2-sum operations. As applications, we compute the number of spanning trees of some special 2-separable graphs. Then comparisons are made between the number of spanning trees and the number of acyclic orientations for this family of 2-separable graphs under certain constraints. We also show that a factorization formula exists for the sum of weights of spanning trees of a special splitting graph.

Recently, it has been noticed that if the graph of an n-by-n complex matrix is a tree, then normality of the matrix is equivalent to three conditions, associated with the edges of the graph, that are much simpler than checking the standard definition of normality. Here, we characterize the precise class of graphs (much more general than trees), for which the three conditions are equivalent to normality, under a slight (and necessary) regularity condition. The graphs are those that are both triangle and 4-cycle free. For triangle-free graphs, normality implies absolute symmetry, under the same regularity condition. The results permit strong applications to real matrices, and to the notions of “principal normality”, and “essentially Hermitian”.

A graph G of order p and size q is called super edge-magic if there exists a bijective function f from V(G) U E(G) to {1, 2, 3, ..., p+q} such that f(x) + f(xy) + f(y) is a constant for every edge $xy \in E(G)$ and f(V(G)) = {1, 2, 3, ..., p}. The super edge-magic deficiency of a graph G is either the smallest nonnegative integer n such that G U nK_1 is super edge-magic or +~ if there exists no such integer n. In this paper, we study the super edge-magic deficiency of join product graphs. We found a lower bound of the super edge-magic deficiency of join product of any connected graph with isolated vertices and a better upper bound of the super edge-magic deficiency of join product of super edge-magic graphs with isolated vertices. Also, we provide constructions of some maximal graphs, ie. super edge-magic graphs with maximal number of edges.

We develop an algorithm for computing the characteristic polynomial of matrices related to threshold graphs. We use this as tool to exhibit, for any natural number n ≥ 4 , 2 n − 4 graphs with n vertices that have a non isomorphic pair with the same signless Laplacian spectrum. We also show how to construct infinite families of pairs of non isomorphic graphs having the same Q -spectrum.

We show that f ( x ) = ⌊ 3 2 x ⌋ is a θ -bounding function for the class of subcubic graphs and that it is best possible. This generalizes a result by Henning et al. (2012), who showed that θ ( G ) ≤ 3 2 α ( G ) for any subcubic triangle-free graph G . Moreover, we provide a θ -bounding function for the class of K 4 -free graphs with maximum degree at most 4 . Finally, we study the problem Clique Cover for subclasses of planar graphs and graphs with bounded maximum degree: in particular, answering a question of Cerioli et al. (2008), we show it admits a PTAS for planar graphs.

In this paper, we determine upper bounds on the algebraic connectivity, denoted as a(G), of maximal outerplanar graphs. We show that if G is a maximal outerplanar graph on n12 vertices not of the form K1Pn1, then a(G)1 with equality holding for exactly two maximal outerplanar graphs on 12 vertices. We show this by assigning labels y1,,yn to the vertices and showing the existence of vertex labellings such that uvE(G)(yuyv)2vV(G)yv2

Let G be a graph. A set S of vertices in Gdominates the graph if every vertex of G is either in S or a neighbor of a vertex in S. Finding a minimum cardinality set which dominates the graph is an NP-complete problem. The graph G is well-dominated if all its minimal dominating sets are of the same cardinality. The complexity status of recognizing well-dominated graphs is not known. We show that recognizing well-dominated graphs can be done polynomially for graphs without cycles of lengths 4 and 5, by proving that a graph belonging to this family is well-dominated if and only if it is well-covered.Assume that a weight function w is defined on the vertices of G. Then G is w-well-dominated if all its minimal dominating sets are of the same weight. We prove that the set of weight functions w such that G is w-well-dominated is a vector space, and denote that vector space by WWD(G). We show that WWD(G) is a subspace of WCW(G), the vector space of weight functions w such that G is w-well-covered. We provide a polynomial characterization of WWD(G) for the case that G does not contain cycles of lengths 4, 5, and 6.

A tree containing exactly two non-pendant vertices is called a double-star. A double-star with degree sequence (k1 + 1, k2 + 1, 1, . . . , 1) is denoted by Sk1,k2. We study the edge-decomposition of graphs into double-stars. It was proved that every double-star of size k decomposes every 2k-regular graph. In this paper, we extend this result by showing that every graph in which every vertex has degree 2k + 1 or 2k + 2 and containing a 2-factor is decomposed into Sk1,k2 and Sk1−1,k2, for all positive integers k1 and k2 such that k1 + k2 = k.

A graph is said to be half-arc-transitive if its automorphism group acts transitively on its vertex set and its edge set, but not on its arc set. In 1970 I. Z. Bouwer constructed an infinite family of vertex- and edge-transitive graphs for each even valence greater than 2 and proved that a subfamily of the constructed graphs, containing one graph for each even valence greater than 2, consists of half-arc-transitive graphs. In a recent paper Conder and Žitnik gave a complete classification of the half-arc-transitive Bouwer graphs. In this paper we generalize the Bouwer graphs to obtain a much larger family of vertex- and edge-transitive graphs, containing almost all so-called tightly attached quartic half-arc-transitive graphs. We give a complete classification of the half-arc-transitive members of this new family of graphs. All half-arc-transitive members are tightly attached.

The paper investigates relationship between algebraic expressions and labeled graphs. We consider directed grid graphs having m rows and n columns. Our intent is to simplify the expressions of these graphs. With that end in view, we describe two algorithms which generate expressions of polynomial sizes for directed grid graphs.

In the article (Mohar, 2016 [9] ), Mohar determined all mixed graphs with H-rank 2, and used it to classify cospectral graphs with respect to their Hermitian adjacency matrix, constructing a class of graphs which can not be determined by their H-spectrum. In the present paper, we investigate the H-rank of mixed graphs further, determining the H-ranks of those mixed graphs with trees, cycles and complete bipartite graphs as underlying graphs, respectively. Moreover, we characterize all mixed graphs with H-rank 3, and show that all connected mixed graphs with H-rank 3 can be determined by their H-spectrum.

Wireless sensor networks are commonly used to monitor various environmental conditions. Possible geometries for the region covered by a sensor include disks, wedges, and rays, among others, depending on the function of the sensor. In this paper we consider a network consisting of ray sensors deployed to detect intruders traversing a path, not necessarily straight, from a source to a destination . The coverage of the network with respect to and can be modeled by a tripartite graph, the barrier graph of the network. While all barrier graphs are tripartite, the converse is not true (for instance, C5 is not a barrier graph).The main result of this paper is a rigidity theorem on the structure of barrier graphs that results from constraints imposed by the geometry of the network. This allows us to show that almost all bipartite graphs are not barrier graphs, despite the fact that various classes of bipartite graphs, including trees, cycles of even length, and Km,n are barrier graphs. Furthermore, vertex cover of a barrier graph corresponds to a set of sensors whose removal allows a clear path from to . While all bipartite graphs with small vertex covers are barrier graphs (a fact we prove for sizes less than 4), the rigidity property also implies that graphs with vertex covers bigger than a certain constant are not barrier graphs.