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.

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.

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

In this paper, we introduce the notions of m-shadow graphs and n-splitting graphs,m ≥ 2, n ≥ 1. We prove that, the m-shadow graphs for paths, complete bipartite graphs and symmetric product between paths and null graphs are odd graceful. In addition, we show that, the m-splitting graphs for paths, stars and symmetric product between paths and null graphs are odd graceful. Finally, we present some examples to illustrate the proposed theories.

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 .

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 ) .

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.

An interconnection network is usually modelled by an undirected graph in which vertices represent processors or memory modules, and edges represent communication links. It is known that the symmetric properties of a graph (such as the vertex regularity, vertex transitivity, edge transitivity, arc transitivity) are the better parameters to measure the stability and synchronizability of an interconnection network. In this paper, we study a subclass of pentavalent symmetric graphs of cube-free order, that is, the case of order 36 p , where p is a prime. A complete classification is given of such graphs. As a byproduct, the classification result includes a non-quasiprimitive graph admitting a quasiprimitive 2-arc-transitive group action. To our knowledge, this is the first known example in pentavalent 2-arc-transitive graphs.

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.

We study spanning properties of sparse cone-based graphs of constant degree, parameterized by a positive integer k > 1 . Cone-based graphs partition the space around each vertex into k equiangular cones, and select at most one outgoing edge in each cone. This guarantees an out-degree of at most k, but the in-degree may be unbounded. To bound the in-degree, at most one incoming edge is retained in each cone. This yields a sparse graph of degree at most 2k (in-degree k and out-degree k). In this paper we introduce the notion of canonical k-cone graphs and establish a spanning ratio of 16.76 for this class of graphs, provided that k = 6 k ′ and k ′ ≥ 5 . The spanning ratio decreases to 4.64 as k ′ increases to 8. We show that both Yao–Yao and Theta–Theta graphs are canonical k-cone graphs and therefore they inherit these spanning ratios. Yao–Yao and Theta–Theta graphs differ only in the way edges are selected. Yao–Yao graphs select an edge of minimum Euclidean length, whereas Theta–Theta graphs select an edge of minimum orthogonal projection onto the cone bisector.

We introduce the family of $k$-gap-planar graphs for $k \geq 0$, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most $k$ of its crossings. This definition is motivated by applications in edge casing, as a $k$-gap-planar graph can be drawn crossing-free after introducing at most $k$ local gaps per edge. We present results on the maximum density of $k$-gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of $k$-gap-planar complete graphs, and the computational complexity of recognizing $k$-gap-planar graphs., Comment: A preliminary version of this paper appeared in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)

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.

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.

International audience; Graph edit distance (GED) is a powerful and flexible graph matching paradigm that can be used to address different tasks in structural pattern recognition, machine learning, and data mining. In this paper, some new binary linear programming formulations for computing the exact GED between two graphs are proposed. A major strength of the formulations lies in their genericity since the GED can be computed between directed or undirected fully attributed graphs (i.e. with attributes on both vertices and edges). Moreover, a relaxation of the domain constraints in the formulations provides efficient lower bound approximations of the GED. A complete experimental study comparing the proposed formulations with 4 state-of-the-art algorithms for exact and approximate graph edit distances is provided. By considering both the quality of the proposed solution and the efficiency of the algorithms as performance criteria, the results show that none of the compared methods dominates the others in the Pareto sense. As a consequence, faced to a given real-world problem, a trade-off between quality and efficiency has to be chosen w.r.t. the application constraints. In this context, this paper provides a guide that can be used to choose the appropriate method.

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.

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.

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.

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] .

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.

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...

Let $G$ be a graph with eigenvalues $lambda_1(G)geqcdotsgeqlambda_n(G)$. In this paper we find all simple graphs $G$ such that $G$ has at most twelve vertices and $G$ has exactly two non-negative eigenvalues. In other words we find all graphs $G$ on $n$ vertices such that $nleq12$ and $lambda_1(G)geq0$, $lambda_2(G)geq0$ and $lambda_3(G) 0$, $lambda_2(G)>0$ and $lambda_3(G)

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.

A novel graph structure modeling a linear time invariant system following the Laplacian dynamics is proposed. This structure is based on the combination of two graphs and each of them has exactly two vertices with the same degree. It is shown that if the difference of vertex numbers of the two graphs is at most one then the combined graph is controllable by a single controller. A sufficient condition concerning the vertex selection for receiving control signals to guarantee the controllability of the combined graph is also proposed. This structure features a small sum of the maximum vertex degree and the diameter compared to some well-known controllable graphs. Numerical examples are provided to illustrate our work.

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.

Nowhere dense graph classes, introduced by Nesetril and Ossona de Mendez, form a large variety of classes of "sparse graphs" including the class of planar graphs, actually all classes with excluded minors, and also bounded degree graphs and graph classes of bounded expansion. We show that deciding properties of graphs definable in first-order logic is fixed-parameter tractable on nowhere dense graph classes. At least for graph classes closed under taking subgraphs, this result is optimal: it was known before that for all classes C of graphs closed under taking subgraphs, if deciding first-order properties of graphs in C is fixed-parameter tractable, then C must be nowhere dense (under a reasonable complexity theoretic assumption). As a by-product, we give an algorithmic construction of sparse neighbourhood covers for nowhere dense graphs. This extends and improves previous constructions of neighbourhood covers for graph classes with excluded minors. At the same time, our construction is considerably simpler than those. Our proofs are based on a new game-theoretic characterisation of nowhere dense graphs that allows for a recursive version of locality-based algorithms on these classes. On the logical side, we prove a "rank-preserving" version of Gaifman's locality theorem., 30 pages

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 total generalised colourings considered in this paper are colourings of the vertices and of the edges of graphs satisfying the following conditions:each set of vertices of the graph which receive the same colour induces an m-degenerate graph,each set of edges of the graph which receive the same colour induces an n-degenerate graph, andincident elements receive different colours. Bounds for the least number of colours with which this can be done for all k-degenerate graphs are obtained. We deal with k-degenerate graphs that are interesting for many practical applications, e.g. WSN design.We study generalised total colourings of graphs with respect to k-degenerate properties.We find an upper bound and a lower bound for the associated chromatic number.

The domination game is played on an arbitrary graph G by two players, Dominator and Staller. The game is called Game 1 when Dominator starts it, and Game 2 otherwise. In this paper bluff graphs are introduced as the graphs in which every vertex is an optimal start vertex in Game 1 as well as in Game 2. It is proved that every minus graph (a graph in which Game 2 finishes faster than Game 1) is a bluff graph. A non-trivial infinite family of minus (and hence bluff) graphs is established. minus graphs with game domination number equal to 3 are characterized. Double bluff graphs are also introduced and it is proved that Kneser graphs K(n, 2), n ≥ 6, are double bluff. The domination game is also studied on generalized Petersen graphs and on Hamming graphs. Several generalized Petersen graphs that are bluff graphs but not vertex-transitive are found. It is proved that Hamming graphs are not double bluff.

We describe an algorithm for generating all k-critical H-free graphs, based on a method of Hoang et al. (A graph G is k-critical H-free if G is H-free, k-chromatic, and every H-free proper subgraph of G is (k−1)-colorable). Using this algorithm, we prove that there are only finitely many 4-critical (P7,Ck)-free graphs, for both k=4 and k=5. We also show that there are only finitely many 4-critical (P8,C4)-free graphs. For each of these cases we also give the complete lists of critical graphs and vertex-critical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the 3-colorability problem in the respective classes. In addition, we prove a number of characterizations for 4-critical H-free graphs when H is disconnected. Moreover, we prove that for every t, the class of 4-critical planar Pt-free graphs is finite. We also determine all 52 4-critical planar P7-free graphs. We also prove that every P11-free graph of girth at least five is 3-colorable, and show that this is best possible by determining the smallest 4-chromatic P12-free graph of girth at least five. Moreover, we show that every P14-free graph of girth at least six and every P17-free graph of girth at least seven is 3-colorable. This strengthens results of Golovach et al.

In this paper, we give lower bounds of vertex and edge forwarding indices for cartesian product, join, composition, disjunction and symmetric difference of graphs. Moreover, we derive further lower bounds for several operators on connected graphs, such as subdivision graph and total graphs.

We prove that, for fixed k ≥ 3, the following classes of labeled n-vertex graphs are asymptotically equicardinal: graphs of diameter k, connected graphs of diameter at least k, and (not necessarily connected) graphs with a shortest path of length at least k. An asymptotically exact approximation of the number of such n-vertex graphs is obtained, and an explicit error estimate in the approximation is found. Thus, the estimates are improved for the asymptotic approximation of the number of n-vertex graphs of fixed diameter k earlier obtained by Furedi and Kim. It is shown that almost all graphs of diameter k have a unique pair of diametrical vertices but almost all graphs of diameter 2 have more than one pair of such 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.

To bound the size (the number of edges) of a graph in terms of other parameters of a graph forms an important family of problems in the extremal graph theory. We present a number of upper bounds on the size of general graphs and triangle-free graphs. We bound the size of any graph and of any triangle-free graph in terms of its order (number of vertices), diameter and edge-connectivity. We also give an upper bound on the size of triangle-free graphs of given order, diameter and minimum degree. All bounds presented in this paper are asymptotically sharp.

We extend to infinite graphs the matroidal characterization of finite graph duality, that two graphs are dual iff they have complementary spanning trees in some common edge set. The naive infinite analogue of this fails. The key in an infinite setting is that dual trees must share between them not only the edges of their host graphs but also their ends: the statement that a set of edges is acyclic and connects all the vertices in one of the graphs iff the remaining edges do the same in its dual will hold only once each of the two graphs' common ends has been assigned to one graph but not the other, and ‘cycle’ and ‘connected’ are interpreted topologically in the space containing the respective edges and precisely the ends thus assigned. This property characterizes graph duality: if, conversely, the spanning trees of two infinite graphs are complementary in this end-sharing way, the graphs form a dual pair.

In 1966 Gallai asked whether all longest paths in a connected graph have nonempty intersection. This is not true in general and various counterexamples have been found. However, the answer to Gallai's question is positive for several well-known classes of graphs, as for instance connected outerplanar graphs, connected split graphs, and 2-trees. A graph is series-parallel if it does not contain $K_4$ as a minor. Series-parallel graphs are also known as partial 2-trees, which are arbitrary subgraphs of 2-trees. We present a proof that every connected series-parallel graph has a vertex that is common to all of its longest paths. Since 2-trees are maximal series-parallel graphs, and outerplanar graphs are also series-parallel, our result captures these two classes in one proof and strengthens them to a larger class of graphs. We also describe how this vertex can be found in linear time., Comment: 17 pages

The energy of a graph G, denoted by E ( G ) , is defined as the sum of the absolute values of all eigenvalues of G. In this paper we present some new lower bounds for energy of non-singular graphs, connected non-singular graphs and connected unicyclic non-singular graphs in terms of number of vertices, number of edges, maximum degree and Zagreb indices.

We found the Lindenmayer systems for line graphs built on selected fractals. We show that the fractal dimension of such obtained graphs in all analysed cases is the same as for their original graphs. Both for the original graphs and for their line graphs we identified classes of nodes which reflect symmetry of the graph.

We determine the book thickness of all zero-divisor graphs with genus at most one. We also describe four families of three page embeddable zero-divisor graphs.

The reliability polynomial (G,p) gives the probability that a graph is connected given each edge may fail independently with probability 1p. Two graphs are reliability equivalent if they have the same reliability polynomial. It is well-known that the reliability polynomial can factorise into the reliability polynomials of the blocks of a graph. We give an infinite family of graphs that have no cutvertex but factorise into reliability polynomials of graphs of smaller order.Brown and Colbourn commented that it was not known if there exist pairs of reliability equivalent graphs with different chromatic numbers. We show that there are infinitely many pairs of reliability equivalent graphs where one graph in each pair has chromatic number 3 and the other graph has chromatic number 4.

Every critical graph is connected on proper edge-colorings of simple graphs. In contrast, there not only exist connected critical graphs but exist disconnected critical graphs on \(g_c\)-colorings of simple graphs. In this article, disconnected \(g_c\)-critical graphs are studied firstly and their structure characteristics are depicted.

A unit disk graph is a c -strip graph if it has a unit disk representation in which all centers of the unit disks lie between two parallel lines at distance c . The classes of c -strip graphs for various c are studied in the literature. For example, the 0-strip graphs are exactly the unit interval graphs, and every 3 / 2 -strip graph is a co-comparability graph. In this paper, we introduce the class of thin strip graphs and study their properties. A graph is a thin strip graph if it is a c -strip graph for every c > 0 . We show that there is no constant t such that the t -strip graphs are exactly the thin strip graphs. We also show that the class of thin strip graphs properly includes the class of mixed unit interval graphs.

We consider several graphs classes defined in terms of conditions on cliques and stable sets, including CIS, split, equistable, and other related classes. We pursue a systematic study of the relations between them. As part of this study, we introduce two generalizations of CIS graphs, obtain a new characterization of split graphs, and a characterization of CIS line graphs.

A graph G = ( V , E ) is a threshold tolerance graph if each vertex v ∈ V can be assigned a weight w v and a tolerance t v such that two vertices x , y ∈ V are adjacent if w x + w y ≥ min ( t x , t y ) . Currently, the most efficient recognition algorithm for threshold tolerance graphs is the algorithm of Monma, Reed, and Trotter which has an O ( n 4 ) runtime. We give an O ( n 2 ) algorithm for recognizing threshold tolerance and their complements, the co-threshold tolerance (co-TT) graphs, resolving an open question of Golumbic, Weingarten, and Limouzy.

This paper is devoted to a detailed study of nowhere-zero flows on signed eulerian graphs. We generalise the well-known fact about the existence of nowhere-zero $2$-flows in eulerian graphs by proving that every signed eulerian graph that admits an integer nowhere-zero flow has a nowhere-zero $4$-flow. We also characterise signed eulerian graphs with flow number $2$, $3$, and $4$, as well as those that do not have an integer nowhere-zero flow. Finally, we discuss the existence of nowhere-zero $A$-flows on signed eulerian graphs for an arbitrary abelian group~$A$., 17 pages, 1 figure

A graph $G$ is a \emph{max point-tolerance (MPT)} graph if each vertex $v$ of $G$ can be mapped to a \emph{pointed-interval} $(I_v, p_v)$ where $I_v$ is an interval of $\mathbb{R}$ and $p_v \in I_v$ such that $uv$ is an edge of $G$ iff $I_u \cap I_v \supseteq \{p_u, p_v\}$. MPT graphs model relationships among DNA fragments in genome-wide association studies as well as basic transmission problems in telecommunications. We formally introduce this graph class, characterize it, study combinatorial optimization problems on it, and relate it to several well known graph classes. We characterize MPT graphs as a special case of several 2D geometric intersection graphs; namely, triangle, rectangle, L-shape, and line segment intersection graphs. We further characterize MPT as having certain linear orders on their vertex set. Our last characterization is that MPT graphs are precisely obtained by intersecting special pairs of interval graphs. We also show that, on MPT graphs, the maximum weight independent set problem can be solved in polynomial time, the coloring problem is NP-complete, and the clique cover problem has a 2-approximation. Finally, we demonstrate several connections to known graph classes; e.g., MPT graphs strictly contain interval graphs and outerplanar graphs, but are incomparable to permutation, chordal, and planar graphs., Accepted to the Journal of Discrete Applied Mathematics