Search

The Degree/Diameter Problem is an extremal problem in graph theory with applications in network design. One of the main research areas in the Degree/Diameter Problem consists of finding large graphs whose order approach the theoretical upper bounds as much as possible. In the case of directed graphs there exist some families that come close to the theoretical upper bound asymptotically. In the case of undirected graphs there also exist some good constructions for specific values of the parameters involved (degree and/or diameter). One such construction was given by McKay, Miller, and Siraň in [McKay, B., M. Miller and J. Siraň, A note on large graphs of diameter two and given maximum degree, J Comb Theo Ser B 74 (1998), 110-118], which produces large graphs of diameter 2 with the aid of the voltage assignment technique. Here we show how to re-engineer the McKay-Miller-Siraň construction in order to obtain large mixed graphs of diameter 2, i.e. graphs containing both directed arcs and undirected edges.

This paper considers the problem of inferring a graph from the number of occurrences of vertex-labeled paths, which is closely related to the pre-image problem for graphs: to reconstruct a graph from its feature space representation. It is shown that both exact and approximate versions of the problem can be solved in polynomial time in the size of an output graph by using dynamic programming algorithms if the graphs are trees whose maximum degree is bounded by a constant and the lengths of given paths and alphabet size are bounded by constants. On the other hand, it is shown that this problem is strongly NP-hard even for trees of bounded degree if the maximum length of paths is not bounded. The problem of inferring a string from the number of occurrences of fixed size substrings is also studied.

In this note, the 〈t〉-properties of five classes of graphs are studied. We prove that the classes of cographs and clique perfect graphs without isolated vertices satisfy the 〈2〉-property and the 〈3〉-property, but do not satisfy the 〈t〉-property for t≥4. The 〈t〉-properties of the planar graphs and the perfect graphs are also studied. We obtain a necessary and sufficient condition for the trestled graph of index k to satisfy the 〈2〉-property.

International audience; We present subexponential parameterized algorithms on planar graphs for a family of problems of the following shape: given a graph, find a connected (induced) subgraph with bounded maximum degree and with maximum number of edges (or vertices). These problems are natural generalisations of the Longest Path problem. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints.

We present O(n3) embedding algorithms (subgraph isomorphism and its generalizations) for classes of graphs of bounded pathwidth, where n is the number of vertices in the graph. These include the first polynomial-time algorithm for minor containment and the first O(nc) algorithm (c a constant independent of k) for topological embedding of graphs from subclasses of partial k-trees, as well as an O(n2) algorithm for subgraph isomorphism. Of independent interest are structural properties of k-connected graphs of bounded pathwidth on which our algorithms are based. We also describe special cases which reduce to various generalizations of string matching, permitting more efficient solutions. Finally, we describe nk+O(1) algorithms for solving these problems on arbitrary graphs of pathwidth at most k.

A conjecture by D. Seese states that if a set of graphs has a decidable monadic second-order theory, then it is the image of a set of trees under a transformation of relational structures defined by monadic second-order formulas, or equivalently, has bounded clique-width. We prove that this conjecture is true if and only if it is true for the particular cases of bipartite undirected graphs, of directed graphs, of partial orders and of comparability graphs. We also prove that it is true for line graphs, for interval graphs and for partial orders of dimension 2. Our treatment of certain countably infinite graphs uses a representation of countable linear orders by binary trees that can be constructed by monadic second-order formulas. By using a counting argument, we show the intrinsic limits of the methods used here to handle this conjecture.

Modifying a given graph to obtain another graph is a well-studied problem with applications in many fields. Given two input graphs G and H, the Contractibility problem is to decide whether H can be obtained from G by a sequence of edge contractions. This problem is known to be NP-complete already when both input graphs are trees of bounded diameter. We prove that Contractibility can be solved in polynomial time when G is a trivially perfect graph and H is a threshold graph, thereby giving the first classes of graphs of unbounded treewidth and unbounded degree on which the problem can be solved in polynomial time. We show that this polynomial-time result is in a sense tight, by proving that Contractibility is NP-complete when G and H are both trivially perfect graphs, and when G is a split graph and H is a threshold graph. If the graph H is fixed and only G is given as input, then the problem is called H-Contractibility. This problem is known to be NP-complete on general graphs already when H is a path on four vertices. We show that, for any fixed graph H, the H-Contractibility problem can be solved in polynomial time if the input graph G is a split graph.

For non-negative real x"0 and simple graph G, @l"x"""0","1(G) is the minimum span over all labelings that assign real numbers to the vertices of G such that adjacent vertices receive labels that differ by at least x"0 and vertices at distance two receive labels that differ by at least 1. In this paper, we introduce the concept of @l-invertibility: G is @l-invertible if and only if for all positive x, @l"x","1(G)[email protected]"1"x","1(G^c). We explore the conditions under which a graph is @l-invertible, and apply the results to the calculation of the function @l"x","1(G) for certain @l-invertible graphs G. We give families of @l-invertible graphs, including certain Kneser graphs, line graphs of complete multipartite graphs, and self-complementary graphs. We also derive the complete list of all @l-invertible graphs with maximum degree 3.

A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H equals the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color equals the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The complete lists of minimal forbidden induced subgraphs for the classes of clique-perfect and coordinated graphs are not known, but some partial characterizations have been obtained. In this paper, we characterize clique-perfect and coordinated graphs by minimal forbidden induced subgraphs when the graph is either paw-free or {gem, W4, bull}-free, both superclasses of triangle-free graphs. © 2009 Elsevier B.V. All rights reserved. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Soulignac, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.

We first present new structural properties of a two-pair in various graphs. A two-pair is used in a well-known characterization of weakly chordal graphs. Based on these properties, we prove the main theorem: a graph G is a weakly chordal (K"2","3,4P"2@?,P"2@?P"4@?,P"6@?,H"1,H"2,H"3)-free graph if and only if G is an edge intersection graph of subtrees on a tree with maximum degree 4. This characterizes the so called [4, 4, 2] graphs. The proof of the theorem constructively finds the representation. Thus, we obtain an algorithm to construct an edge intersection model of subtrees on a tree with maximum degree 4 for such a given graph. This is a recognition algorithm for [4, 4, 2] graphs.

Gavril [F. Gavril, Maximum weight independent sets and cliques in intersection graphs of filaments, Inform. Process. Lett. 73 (2000) 181–188] defined two new families of intersection graphs: the interval-filament graphs and the subtree-filament graphs. The complements of interval-filament graphs are the cointerval mixed graphs and the complements of subtree-filament graphs are the cochordal mixed graphs. The family of interval-filament graphs contains the families of cocomparability, polygon-circle, circle and chordal graphs.In the present paper we introduce a generalization of the subtree-filament graphs, namely, the 3D-interval-filament graphs. We prove that the family of 3D-interval-filament graphs, the family of complements of co(interval-filament) mixed graphs and the family of overlap graphs of interval-filaments are the same, and show that every 3D-interval-filament graph has an intersection representation by a family of piecewise linear filaments. We use the properties of these graphs to describe an algorithm for maximum weight holes of a given parity in 3D-interval-filament graphs and an algorithm for antiholes of a given parity in interval-filament and subtree-filament graphs.We define various subfamilies of 3D-interval-filament graphs and characterize them as overlap graphs and as complements of H-mixed graphs.

The maximum number of vertices in a graph of specified degree and diameter cannot exceed the Moore bound. Graphs achieving this bound are called Moore graphs. Because Moore graphs are so rare, researchers have considered various relaxations of the Moore graph constraints. Since the diameter of a Moore graph is equal to its radius, one can consider graphs in which the condition on the diameter is relaxed, by one, while the condition on the radius is maintained. Such graphs are called radial Moore graphs. It has previously been shown that radial Moore graphs exist for all degrees when the radius is two. In this paper, we extend this result to radius three. We also construct examples that settle the existence question for a few new cases, and summarize the state of knowledge on the problem.

This is the post-print version of the Article - Copyright @ 2010 Elsevier A graph G is loosely-c-connected, or ℓ-c-connected, if there exists a number d depending on G such that the deletion of fewer than c vertices from G leaves precisely one infinite component and a graph containing at most d vertices. In this paper, we give the structure of a set of ℓ-c-connected infinite graphs that form an unavoidable set among the topological minors of ℓ-c-connected infinite graphs. Corresponding results for minors and parallel minors are also obtained. This study was supported in part by NSF grants DMS-1001230 and NSA grant H98230-10-1-0186

The Q-index of a simple graph G is the largest eigenvalue of the matrix Q, the signless Laplacian of G. It is well-known that in the set of connected graphs with fixed order and size, the graphs with maximal Q-index are the nested split graphs (also known as threshold graphs). In this paper, we focus our attention on the eigenvector techniques for getting some (lower and upper) bounds on the Q-index of nested split graphs. In addition, we give some computational results in order to compare these bounds.

We present proofs of lower bounds on the node search number of some grid-like graphs including two-dimensional grids, cylinders, tori and a variation we call “orb-webs”. Node search number is equivalent to pathwidth and vertex separation, which are all important graph parameters. Since matching upper bounds are not difficult to obtain, this implies that the pathwidth of these graphs is easily computed, because the bounds are simple functions of the graph dimensions. We also show matching upper and lower bounds on the node search number of equidimensional tori which are one less than the obvious upper bound.

Let G=(V,E) be a simple graph with vertex set V and edge set E. A subset [email protected][email protected]?E is a mixed dominating set if every element [email protected]?([email protected]?E)@?W is either adjacent or incident to an element of W. The mixed domination problem is to find a minimum mixed dominating set of G. In this paper we first prove that a connected graph is a tree if and only if its total graph is strongly chordal, and thus we obtain a polynomial-time algorithm for this problem in trees. Further we design another linear-time labeling algorithm for this problem in trees. At the end of the paper, we show that the mixed domination problem is NP-complete even when restricted to split graphs, a subclass of chordal graphs.

In this paper, we study a chromatic aspect for the class of P6-free graphs. Here, the focus of our interest are graph classes (defined in terms of forbidden induced subgraphs) for which the question of 3-colorability can be decided in polynomial time and, if so, a proper 3-coloring can be determined also in polynomial time. Note that the 3-colorability decision problem is a well-known NP-complete problem, even for special graph classes, e.g. for triangle- and K1,5-free graphs (Discrete Math. 162 (1–3) (1996) 313–317). Therefore, it is unlikely that there exists a polynomial algorithm deciding whether there exists a 3-coloring of a given graph in general. Our approach is based on an encoding of the problem with Boolean formulas making use of the existence of bounded dominating subgraphs. Together with a structural analysis of the non-perfect K4-free members of the graph class in consideration we obtain our main result that 3-colorability can be decided in polynomial time for the class of P6-free graphs.

This work deals with a generalization of the Cartesian product of graphs, the product graph G"m*G"p introduced by Bermond et al. [J.C. Bermond, C. Delorme, G. Farhi, Large graphs with given degree and diameter II, J. Combin. Theory, Series B 36 (1984), 32-48]. The connectivity of these product graphs is approached by studying the k-restricted edge-connectivity, which is defined as the minimum number of edges of a graph whose deletion yields a disconnected graph with all its components having at least k vertices. To be more precise, we present lower and upper bounds for the k-restricted edge-connectivity of G"m*G"p, and provide sufficient conditions that ensure an optimal value for this parameter. When both G"m and G"p are regular graphs, conditions for guaranteeing that G"m*G"p is [email protected]"("k") are also presented, and the particular case where both G"m and G"p are complete graphs is considered.

Previously the first author has shown how to construct vertex-magic total labelings (VMTLs) for large families of regular graphs. The construction proceeds by successively adding arbitrary 2-factors to a regular graph of order n which possesses a strong VMTL, to produce a regular graph of the same order but larger size. In this paper, we exploit this construction method. We are able to show that for any r>=4, every r-regular graph of odd order [email protected]?17 has a strong VMTL. We show how to produce strong labelings for some families of 2-regular graphs since these are used as the starting points of our construction. While even-order regular graphs are much harder to deal with, we introduce 'mirror' labelings which provide a suitable starting point from which the construction can proceed. We are able to show that several large classes of r-regular graphs of even order (including some Hamiltonian graphs) have VMTLs.

A graph G is well-covered if every maximal independent set has the same cardinality. This paper investigates when the Cartesian product of two graphs is well-covered. We prove that if G and H both belong to a large class of graphs that includes all non-well-covered triangle-free graphs and most well-covered triangle-free graphs, then G×H is not well-covered. We also show that if G is not well-covered, then neither is G×G. Finally, we show that G×G is not well-covered for all graphs of girth at least 5 by introducing super well-covered graphs and classifying all such graphs of girth at least 5.

Ma and Spinrad have shown that every transitive orientation of a chordal comparability graph is the intersection of four linear orders. That is, chordal comparability graphs are comparability graphs of posets of dimension four. Among other uses, this gives an implicit representation of a chordal comparability graph using O(n) integers so that, given two vertices, it can be determined in O(1) time whether they are adjacent, no matter how dense the graph is. We give a linear time algorithm for finding the four linear orders, improving on their bound of O(n2).

There are several density functions for graphs which have found use in various applications. In this paper, we examine two of them, the first being given by b(G)=|E(G)|/|V(G)|, and the other being given by g(G)=|E(G)|/(|V(G)|−ω(G)), where ω(G) denotes the number of components of G. Graphs for which b(H)≤b(G) for all subgraphs H of G are called balanced graphs, and graphs for which g(H)≤g(G) for all subgraphs H of G are called 1-balanced graphs (also sometimes called strongly balanced or uniformly dense in the literature). Although the functions b and g are very similar, they distinguish classes of graphs sufficiently differently that b(G) is useful in studying random graphs, g(G) has been useful in designing networks with reduced vulnerability to attack and in studying the World Wide Web, and a similar function is useful in the study of rigidity. First we give a new characterization of balanced graphs. Then we introduce a graph construction which generalizes the Cartesian product of graphs to produce what we call a generalized Cartesian product. We show that generalized Cartesian product derived from a tree and 1-balanced graphs are 1-balanced, and we use this to prove that the generalized Cartesian products derived from 1-balanced graphs are 1-balanced.

This is a continuation of the study, begun by Ceccherini-Silberstein and Woess (2009) [5], of context-free pairs of groups and the related context-free graphs in the sense of Muller and Schupp (1985) [22]. The graphs under consideration are Schreier graphs of a subgroup of some finitely generated group, and context-freeness relates to a tree-like structure of those graphs. Instead of the cones of Muller and Schupp (1985) [22] (connected components resulting from deletion of finite balls with respect to the graph metric), a more general approach to context-free graphs is proposed via tree sets consisting of cuts of the graph, and associated structure trees. The existence of tree sets with certain “good” properties is studied. With a tree set, a natural context-free grammar is associated. These investigations of the structure of context free pairs, resp. graphs are then applied to study random walk asymptotics via complex analysis. In particular, a complete proof of the local limit theorem for return probabilities on any virtually free group is given, as well as on Schreier graphs of a finitely generated subgoup of a free group. This extends, respectively completes, the significant work of Lalley (1993, 2001) [18,20].

We define a k-limited packing in a graph, which generalizes a packing in a graph, and give several bounds on the size of a k-limited packing. One such bound involves the domination number of the graph, and here we show, when k = 2 , that all trees attaining the bound can be built via a simple sequence of operations. We also consider graphs where every maximal 2-limited packing is a maximum 2-limited packing, and characterize those of girth 14 or more.

We investigate the maximum number of edges in a graph with a prescribed number of 1-factors. We also examine the structure of such extremal graphs.

Let G=(V,E)G=(V,E) be a graph in which every vertex v∈Vv∈V has a weight w(v)⩾0w(v)⩾0 and a cost c(v)⩾0c(v)⩾0. Let SGSG be the family of all maximum-weight stable sets in G . For any integer d⩾0d⩾0, a minimum d-transversal in the graph G with respect to SGSG is a subset of vertices T⊆VT⊆V of minimum total cost such that |T∩S|⩾d|T∩S|⩾d for every S∈SGS∈SG. In this paper, we present a polynomial-time algorithm to determine minimum d-transversals in bipartite graphs. Our algorithm is based on a characterization of maximum-weight stable sets in bipartite graphs. We also derive results on minimum d-transversals of minimum-weight vertex covers in weighted bipartite graphs.