Search

Graph Theory is one of the most flourishing branches of modern Mathematics finding widest applications in all most all branches of Science & Technology. It is applied in diverse areas such as social sciences, linguistics, physical sciences, communication engineering etc. Number Theory is one of the oldest branches of Mathematics, which inherited rich contributions from almost all greatest mathematicians, ancient and modern. Every branch of mathematics employs some notion of a product that enables the combination or decomposition of its elemental structures. Product of graphs are introduced in Graph Theory very recently and developing rapidly. In this paper, we consider direct product graphs of Cayley graphs with Arithmetic graphs and present Matching dominating set of these graphs.

We consider the maximum common connected edge subgraph problem and the maximum common connected induced subgraph problem for simple graphs with labeled vertices (or labeled edges). The former is to find a connected graph with the maximum number of edges that is isomorphic to a subgraph of each of the two input graphs. The latter is to find a common connected induced subgraph with the maximum number of vertices. We prove that both problems are NP-hard for 3-outerplanar labeled graphs even if the maximum vertex degree is bounded by 4. Since the reductions used in the proofs construct graphs with treewidth at most 4, both problems are NP-hard also for such graphs, which significantly improves the previous hardness results for graphs with treewidth 11. We also present improved exponential-time algorithms for both problems on labeled graphs of bounded treewidth and bounded vertex degree.

We investigate three formalisms to specify graph languages, i.e. sets of graphs, based on type graphs. First, we are interested in (pure) type graphs, where the corresponding language consists of all graphs that can be mapped homomorphically to a given type graph. In this context, we also study languages specified by restriction graphs and their relation to type graphs. Second, we extend this basic approach to a type graph logic and, third, to type graphs with annotations. We present decidability results and closure properties for each of the formalisms., (v2): -Fixed some typos -Added more references

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 .

International audience; Tree-decompositions are the cornerstone of many dynamic programming algorithms for solving graph problems. Since the complexity of such algorithms generally depends exponentially on the width (size of the bags) of the decomposition, much work has been devoted to compute tree-decompositions with small width. However, practical algorithms computing tree-decompositions only exist for graphs with treewidth less than 4. In such graphs, the time-complexity of dynamic programming algorithms is dominated by the size (number of bags) of the tree-decompositions. It is then interesting to minimize the size of the tree-decompositions. In this extended abstract, we consider the problem of computing a tree-decomposition of a graph with width at most k and minimum size. We prove that the problem is NP-complete for any fixed k ≥ 4 and polynomial for k ≤ 2; for k = 3, we show that it is polynomial in the class of trees and 2-connected outerplanar graphs.

A graph is even-hole-free if it has no induced even cycles of length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this paper, we consider (cap, even hole)-free graphs, and more generally, (cap, 4-hole)-free odd-signable graphs. We give an explicit construction of these graphs. We prove that every such graph G has a vertex of degree at most 3 2 ω ( G ) − 1 , and hence χ ( G ) ≤ 3 2 ω ( G ) , where ω ( G ) denotes the size of a largest clique in G and χ ( G ) denotes the chromatic number of G . We give an O ( n m ) algorithm for q -coloring these graphs for fixed q and an O ( n m ) algorithm for maximum weight stable set, where n is the number of vertices and m is the number of edges of the input graph. We also give a polynomial-time algorithm for minimum coloring. Our algorithms are based on our results that triangle-free odd-signable graphs have treewidth at most 5 and thus have clique-width at most 48, and that (cap, 4-hole)-free odd-signable graphs G without clique cutsets have treewidth at most 6 ω ( G ) − 1 and clique-width at most 48.

When a graceful labeling of a bipartite graph places the smaller labels in one of the stable sets of the graph, it becomes an α-labeling. This is the most restrictive type of difference-vertex labeling and it is located at the very core of this research area. Here we use an extension of the adjacency matrix to count and classify α-labeled graphs according to their size, order, and boundary value.

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.

Let GA be a hereditary family of graphs and H a family of acyclically directed graphs. A graph G ( V , E ) is a GA-H reduced graph if it can be obtained from a graph GA ( V , D ) ∈ GA by deleting the edges of an edge subgraph H ( V , E ′ ) ∈ H . The present paper complements reference [9] by proving that the following properties are equivalent: Property 1: u → v ∈ E ′ implies N GA [ u ] ⊆ N GA [ v ] . Property 2: u → v ∈ E ′ and v — w ∉ E ∪ E ′ = D implies u — w ∉ E ∪ E ′ = D . This equivalence implies that most of the algorithms in the above reference apply to the GA-H reduced graphs where H is the family of transitive edge subgraphs of the closed neighborhoods containment graphs of the graphs in GA. We also describe a polynomial time algorithm for maximum weight independent set under the weaker condition that H ( V , E ′ ) is a locally transitive edge subgraph of the closed neighborhoods containment graph of GA ( V , D ) .

Given a set L of graphs, a graph G is L -free if G does not contain any graph in L as an induced subgraph. There has been keen interest in colouring graphs whose forbidden list L contains graphs with four vertices. A recent paper of Lozin and Malyshev (in press) discusses the state of the art on this problem, identifying three outstanding classes: L = ( 4 K 1 , claw ) , L = ( 4 K 1 , claw, co-diamond ) , and L = ( 4 K 1 , C 4 ) . In this paper we investigate the class of ( 4 K 1 , C 4 , C 5 )-free graphs and show that if G is a ( 4 K 1 , C 4 , C 5 )-free graph, then G either has bounded clique width or is perfect.

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.

For a distance-regular graph of diameter three Γ, the statement that distance-3 graph Γ 3 of Γ is strongly regular is equivalent to that Γ has eigenvalue −1. There are many distance-regular graphs of diameter 3 having eigenvalue −1, such as the folded 7-cube, generalized hexagons of order ( s , s ) and antipodal nonbipartite distance-regular graphs of diameter 3. In this paper, we show that for a fixed positive integer α ( β , respectively), there are only finitely many distance-regular graphs of diameter 3 having eigenvalue −1 and a 3 = α ( b 1 c 2 = β and a 3 ≠ 0 , respectively). Such distance-regular graphs for small numbers α = 1 , 2 or β = 3 with a 3 ≠ 0 are classified. We show that there are no distance-regular graphs with intersection array { 44 , 35 , 3 ; 1 , 5 , 42 } . Moreover, we classify the distance-regular graphs with diameter 3 and smallest eigenvalue greater than −3.

We study the properties of graphs that can be placed in a rectangular lattice so that all vertices located in the same (horizontal or vertical) row be adjacent. Some criterion is formulated for an arbitrary graph to be in the specified class.

A graph is said to be a semi-Cayley graph over a group G if it admits G as a semiregular automorphism group with two orbits of equal size. In this paper, definition of normal edge-transitive, arc-t...

An edge-bicolored graph G = ( V , R ∪ B ) is called Red/Blue-split graph if there exists a partition I B and I R of V such that I B and I R are independent sets in ( V , B ) and ( V , R ) , respectively. Red/Blue-split graphs generalize several well studied graph classes including split graphs, bipartite graphs and Konig–Egervary graphs. In this paper we consider the algorithmic complexity of various optimization problems like minimum edge (or vertex) deletion and maximum edge (or vertex) induced subgraph related to Red/Blue split graphs. All these problems are NP -hard and thus we look at them from algorithmic paradigms that are meant for coping with NP -hardness. We obtain various hardness as well as algorithmic results for these problems in the realm of approximation algorithms and parameterized complexity. The main tool we use to obtain all our results is polynomial time transformations between appropriate problems. On the way, we also resolve some problems related to inapproximability about certain optimization problems mentioned by Korach et al. (2006) [17] .

In the paper Combinatorica 33(2) (2013) 231–252, Huggett and Moffatt characterized all bipartite partial duals of a plane graph in terms of oriented circuits in its medial graph. An open problem posed in their paper is the characterization of Eulerian partial duals of plane graphs. In this article, we solve this problem by considering half-edge orientations of medial graphs.

We consider the problem of reachability in pushdown graphs. We study the problem for pushdown graphs with constant treewidth. Even for pushdown graphs with treewidth 1, for the reachability problem we establish the following: (i) the problem is PTIME-complete, and (ii) any subcubic algorithm for the problem would contradict the k-clique conjecture and imply faster combinatorial algorithms for cliques in graphs. The study of reachability in pushdown systems with constant treewidth restriction.We show the problem remains PTIME-complete even for treewidth 1.We show better algorithms for treewidth 1 imply the same for cliques in graphs.

We discuss the existence of minors of given graphs in optimal 1-planar graphs. As our first main result, we prove that for any graph H, there exists an optimal 1-planar graph which contains H as a topological minor. Next, we consider minors of complete graphs. It is easily obtained from Maders result (Mader, 1968) that every optimal 1-planar graph has a K6-minor. In the paper, we characterize optimal 1-planar graphs having no K7-minor.

The reliability polynomial R ( G , p ) of a finite undirected graph G = ( V , E ) gives the probability that the operational edges of G induce a connected graph assuming that all edges of G fail independently with identical probability q = 1 − p . In this article we investigate the probability that the operational edges of a graph with randomly failing edges induce a biconnected or two-edge connected subgraph, which corresponds to demands for redundancy or higher throughput in communication networks. The computation of the biconnected or two-edge connected reliability for general graphs is computationally intractable (#P-hard). We provide recurrence relations for biconnected and two-edge connected reliability of complete graphs. As a consequence, we can determine the number of biconnected and two-edge connected graphs with given order and size. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 000(00), 000–000 2017

Motivated by applications in network epidemiology, we consider the problem of determining whether it is possible to delete at most k edges from a given input graph (of small treewidth) so that the resulting graph avoids a set $$\mathcal {F}$$ of forbidden subgraphs; of particular interest is the problem of determining whether it is possible to delete at most k edges so that the resulting graph has no connected component of more than h vertices, as this bounds the worst-case size of an epidemic. While even this special case of the problem is NP-complete in general (even when $$h=3$$ ), we provide evidence that many of the real-world networks of interest are likely to have small treewidth, and we describe an algorithm which solves the general problem in time $$2^{O(|\mathcal {F}|w^r)}n$$ on an input graph having n vertices and whose treewidth is bounded by a fixed constant w, if each of the subgraphs we wish to avoid has at most r vertices. For the special case in which we wish only to ensure that no component has more than h vertices, we improve on this to give an algorithm running in time $$O((wh)^{2w}n)$$ , which we have implemented and tested on real datasets based on cattle movements.

Let T be a tree with at least four vertices, none of which has degree 2, embedded in the plane. A Halin graph is a plane graph constructed by connecting the leaves of T into a cycle. Thus the cycle C forms the outer face of the Halin graph, with the tree inside it. Let G be a Halin graph with order n. Denote by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mu(G)$\end{document}μ(G) the Laplacian spectral radius of G. This paper determines all the Halin graphs with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mu(G)\geq n-4$\end{document}μ(G)≥n−4. Moreover, we obtain the graphs with the first three largest Laplacian spectral radius among all the Halin graphs on n vertices.

The class of outerplanar graphs is used for testing the average complexity of algorithms on graphs. A random labeled outerplanar graph can be generated by a polynomial algorithm based on the results of an enumeration of such graphs. By a bicyclic (tricyclic) graph we mean a connected graph with cyclomatic number 2 (respectively, 3). We find explicit formulas for the number of labeled connected outerplanar bicyclic and tricyclic graphs with n vertices and also obtain asymptotics for the number of these graphs for large n. Moreover, we obtain explicit formulas for the number of labeled outerplanar bicyclic and tricyclic n-vertex blocks and deduce the corresponding asymptotics for large n.

Many NP-hard problems on graphs become tractable on graphs of low treewidth, but the corresponding algorithms require access to a tree decomposition of the graph of low (ideally, minimum) width. Unfortunately computation of treewidth is itself NP-hard and a wide variety of exact, heuristic and approximation algorithms have been proposed for this problem. To support this ongoing research we present here ToTo, an open graph database for computation, storage and rapid retrieval of tree decompositions. We hope that the database will become both a central repository for important graphs and benchmark datasets and extend the use of treewidth beyond the usual communities: the database and associated algorithms can be accessed via a web browser and do not require installation of any specialist software. (C) 2016 Elsevier B.V. All rights reserved.

We present constant-work-space polynomial time algorithms for solving the shortest path problem, finding the chromatic polynomial, clique number, number of components, circumference, and girth of cactus graphs and block graphs. For some of these problems we also present in-place algorithms, which perform faster than the corresponding constant-work-space algorithms. The problems considered are fundamental to many areas of graph theory, computational geometry, and combinatorial optimization, and have a wide range of applications including transportation, robotics, and image processing.

Submitted by Domingos Cardoso (dcardoso@ua.pt) on 2016-12-10T23:44:01Z No. of bitstreams: 1 1-s2.0-S0166218X16304486-main.pdf: 403736 bytes, checksum: 101d5d8f6d0ae399f45a4621d288bad0 (MD5) Approved for entry into archive by Bella Nolasco(bellanolasco@ua.pt) on 2017-01-13T12:04:44Z (GMT) No. of bitstreams: 1 1-s2.0-S0166218X16304486-main.pdf: 403736 bytes, checksum: 101d5d8f6d0ae399f45a4621d288bad0 (MD5) Made available in DSpace on 2017-01-13T12:04:44Z (GMT). No. of bitstreams: 1 1-s2.0-S0166218X16304486-main.pdf: 403736 bytes, checksum: 101d5d8f6d0ae399f45a4621d288bad0 (MD5) Previous issue date: 2017-01-30

We give a fixed-parameter tractable algorithm that, given a parameter $k$ and two graphs $G_1,G_2$, either concludes that one of these graphs has treewidth at least $k$, or determines whether $G_1$ and $G_2$ are isomorphic. The running time of the algorithm on an $n$-vertex graph is $2^{O(k^5\log k)}\cdot n^5$, and this is the first fixed-parameter algorithm for Graph Isomorphism parameterized by treewidth. Our algorithm in fact solves the more general canonization problem. We namely design a procedure working in $2^{O(k^5\log k)}\cdot n^5$ time that, for a given graph $G$ on $n$ vertices, either concludes that the treewidth of $G$ is at least $k$, or: * finds in an isomorphic-invariant way a graph $\mathfrak{c}(G)$ that is isomorphic to $G$; * finds an isomorphism-invariant construction term --- an algebraic expression that encodes $G$ together with a tree decomposition of $G$ of width $O(k^4)$. Hence, the isomorphism test reduces to verifying whether the computed isomorphic copies or the construction terms for $G_1$ and $G_2$ are equal., Full version of a paper presented at FOCS 2014

A Halin graph G is a plane graph constructed as follows: Let T be a tree on at least 4 vertices. All vertices of T are either of degree 1, called leaves, or of degree at least 3. Let C be a cycle connecting the leaves of T in such a way that C forms the boundary of the unbounded face. Denote the set of all n -vertex Halin graphs by G n . In this article, sharp upper and lower bounds on the signless Laplacian indices of graphs among G n are determined and the extremal graphs are identified, respectively. As well graphs in G n having the second and third largest signless Laplacian indices are determined, respectively.

A structural characterization of graphs not containing the Wagner graph, also known as V 8 , is shown. The result was announced in 1979 by the second author, but until now a proof has not been published.

Many algorithms have been developed for NP-hard problems on graphs with small treewidth $k$. For example, all problems that are expressable in linear extended monadic second order can be solved in linear time on graphs of bounded treewidth. It turns out that the bottleneck of many algorithms for NP-hard problems is the computation of a tree decomposition of width $O(k)$. In particular, by the bidimensional theory, there are many linear extended monadic second order problems that can be solved on $n$-vertex planar graphs with treewidth $k$ in a time linear in $n$ and subexponential in $k$ if a tree decomposition of width $O(k)$ can be found in such a time. We present the first algorithm that, on $n$-vertex planar graphs with treewidth $k$, finds a tree decomposition of width $O(k)$ in such a time. In more detail, our algorithm has a running time of $O(n k^2 \log k)$. We show the result as a special case of a result concerning so-called weighted treewidth of weighted graphs.

The breadth of problems requiring graph analytics is growing rapidly. Diameter is one of the most important metrics of a graph. The diameter is important in both designing algorithms for graphs and understanding the nature and evolution of graphs. Besides, the real world graphs are always changing. So detecting diameter in both static and dynamic graphs is very important. We first present an algorithm to calculate the diameter of the static graphs. The main goal of this algorithm is to reduce the number of breadth-first searches required to determine diameter of the graph. In addition, another algorithm is presented for calculating the diameter of incremental graphs. This algorithm uses the proposed static algorithm in its body. Based on experimental results, our proposed algorithm can detect diameter of both static and incremental graphs faster than existing approaches. To the best of our knowledge, the second algorithm is the first one that is able to efficiently determine the diameter of disconnected graphs that will be connected over time by adding new vertices.

Treewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This paper surveys several graph parameters tied to treewidth, including separation number, tangle number, well-linked number and Cartesian tree product number. We review many results in the literature showing these parameters are tied to treewidth. In a number of cases we also improve known bounds, provide simpler proofs and show that the inequalities presented are tight., Comment: 22 pages, 1 figure

Given an edge-colored graph, an internal vertex of a path experiences a reload cost if it lies between two consecutive edges of different colors. The value of the reload cost depends only on the colors of the traversed edges. The reload cost concept has important applications in dynamic networks, such as transportation networks and dynamic spectrum access networks. In the minimum changeover cost arborescence (MinCCA) problem, we seek a spanning tree of an edge-colored graph, in which the sum of reload costs of all internal vertices, starting from a given root, is minimized. In general, MinCCA is known to be hard to approximate within factor n 1 - ? , for any ? 0 , on a graph of n vertices.We first show that MinCCA can be optimally solved in polynomial-time on cactus graphs. Our main result is an optimal polynomial-time algorithm for graphs of bounded treewidth, thus establishing the solvability of our problem on a fundamental subclass of graphs. Our results imply that MinCCA is fixed parameter tractable when parameterized by treewidth and the maximum degree of the input graph.

A complete proof that algorithms proposed by the authors solve the problem of minimum-cost transformation of a graph into another graph is given. The problem is solved both by a direct algorithm of linear complexity and by a reduction to quadratic integer linear programming.

For t > 0 and g = 0, a vertex-weighted graph of total weight W is (t, g)-trimmable if it contains a vertex-induced subgraph of total weight at least (1-1/t)W and with no simple path of more than g edges. A family of graphs is trimmable if for every constant t > 0, there is a constant g = 0 such that every vertex-weighted graph in the family is (t, g)-trimmable. We show that every family of graphs of bounded domino treewidth is trimmable. This implies that every family of graphs of bounded degree is trimmable if the graphs in the family have bounded treewidth or are planar. We also show that every family of directed graphs of bounded layer bandwidth (a less restrictive condition than bounded directed bandwidth) is trimmable. As an application of these results, we derive polynomial-time approximation schemes for various forms of the problem of labeling a subset of given weighted point features with nonoverlapping sliding axes-parallel rectangular labels so as to maximize the total weight of the labeled features, provided that the ratios of label heights or the ratios of label lengths are bounded by a constant. This settles one of the last major open questions in the theory of map labeling. Keywords: Trimming weighted graphs - Domino treewidth - Planar graphs - Layer bandwidth - Point-feature label placement - Map labeling - Sliding labels - Polynomial-time approximation schemes.

Consider the following problem: Given a planar graph $G$, what is the maximum number $p$ such that $G$ has a planar straight-line drawing with $p$ collinear vertices? This problem resides at the core of several graph drawing problems, including universal point subsets, untangling, and column planarity. The following results are known for it: Every $n$-vertex planar graph has a planar straight-line drawing with $\Omega(\sqrt{n})$ collinear vertices; for every $n$, there is an $n$-vertex planar graph whose every planar straight-line drawing has $O(n^\sigma)$ collinear vertices, where $\sigma, Journal of Computational Geometry, Vol. 9 No. 1 (2018)