Search

A set S of vertices in a graph G is a connected dominating set of G if S dominates G and the subgraph induced by S is connected. We study the graphs for which adding any edge does not change the connected domination number.Keywords: Connected domination, connected domination stable, edge addition

Let G=(V, E) be a simple connected graph. An induced cycle path partition of G is a partition of V (G) into subsets such that the subsets induce cycles and paths. The minimum order taken over all induced cycle path partitions is called the induced cycle path number of G and is denoted by ρcp(G). In this paper, we dertermine this parameter for some standard graphs and investigate the same for unicyclic graphs and Halin graphs. We also obtain an upper bound for arbitrary graphs and characterize the extremal graphs. The graphs which have unique induced cycle path partition are also discussed

An edge of G is singular if it does not lie on any triangle of G ; otherwise, it is non-singular. A vertex u of a graph G is called locally connected if the induced subgraph G N ( u ) ] by its neighborhood is connected; otherwise, it is called locally disconnected.In this paper, we prove that if a connected claw-free graph G of order at least three satisfies the following two conditions: For each locally disconnected vertex v of G with degree at least 3, there is a nonnegative integer s such that v lies on an induced cycle of length at least 4 with at most s non-singular edges and with at least s - 3 locally connected vertices; for each locally disconnected vertex v of G with degree 2, there is a nonnegative integer s such that v lies on an induced cycle C with at most s non-singular edges and with at least s - 2 locally connected vertices and such that the subgraph induced by those vertices of C that have degree two in G is a path or a cycle, then G is Hamiltonian, and it is best possible in some sense.Our result is a common extension of two known results in Bielak (2000) and in Li (2002); hence also of the results in Oberly and Sumner (1979) and in Ryjacek (1990).

The proper connection number $pc(G)$ of a connected graph $G$ is defined as the minimum number of colors needed to color its edges, so that every pair of distinct vertices of $G$ is connected by at least one path in $G$ such that no two adjacent edges of the path are colored the same, and such a path is called a proper path. In this paper, we show that for every connected graph with diameter 2 and minimum degree at least 2, its proper connection number is 2. Then, we give an upper bound $\frac{3n}{\delta + 1}-1$ for every connected graph of order $n$ and minimum degree $\delta$. We also show that for every connected graph $G$ with minimum degree at least $2$, the proper connection number $pc(G)$ is upper bounded by $pc(G[D])+2$, where $D$ is a connected two-way (two-step) dominating set of $G$. Bounds of the form $pc(G)\leq 4$ or $pc(G)=2$, for many special graph classes follow as easy corollaries from this result, which include connected interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs and chain graphs, all with minimum degree at least $2$. Furthermore, we get the sharp upper bound 3 for the proper connection numbers of interval graphs and circular arc graphs through analyzing their structures., Comment: 12 pages. arXiv admin note: text overlap with arXiv:1010.2296 by other authors

The complexity of the subgraph isomorphism problem where the pattern graph is of fixed size is well known to depend on the topology of the pattern graph. Here, we present two results which, in contrast, provide evidence that no topology of an induced subgraph of fixed size can be substantially easier to detect or count than an independent set of related size.We show that any fixed pattern graph having a maximum independent set of size k that is disjoint from other maximum independent sets is not easier to detect as an induced subgraph than an independent set of size k. It follows in particular that an induced path on 2 k - 1 vertices is not easier to detect than an independent set on k vertices, and that an induced cycle on 2k vertices is not easier to detect than an independent set on k vertices. In view of linear time upper bounds on the detection of induced path of length two and three, our lower bound is tight. Similar corollaries hold for the detection of induced complete bipartite graphs and an induced paw and its generalizations.We show also that for an arbitrary pattern graph H on k vertices with no isolated vertices, there is a simple subdivision of H, resulting from splitting each edge into a path of length four and attaching a distinct path of length three at each vertex of degree one, that is not easier to detect or count than an independent set on k vertices, respectively.Next, we show that the so-called diamond and its generalizations on k vertices are not easier to detect as induced subgraphs than an independent set on three vertices or an independent set on k vertices, respectively. For C 4 , we give a weaker evidence of its hardness in terms of an independent set on three vertices.Finally, we derive several results relating the complexity of the edge-colored variant of induced subgraph isomorphism to that of the standard variant.

The Maximum Independent Set problem is NP-hard and remains NP-hard for graphs of maximum degree at most three (also called subcubic graphs). In this paper, we will study its complexity in subclasses of subcubic graphs.Let S i , j , k be the graph consisting of three induced paths of lengths i , j and k , with a common initial vertex and A q l be the graph consisting of an induced cycle C q ( q ? 3 ) and an induced path with l edges having an end-vertex in common with the C q . For example S 0 , 0 , l and A 4 1 are known as path of length l and banner, respectively.Our main result is that the Maximum Independent Set problem can be solved in polynomial time in the class of subcubic, ( S 2 , j , k , A 5 l ) -free graphs.

We study the problem of computing K-terminal reliability for two subclasses of chordal graphs.We show that computing the K-terminal reliability of a directed path graph is #P-complete.We propose an O ( n 2 ) -time algorithm for computing the K-terminal reliability of a rooted directed path graph. Let G denote a graph, and K ? V ( G ) represent a set of target vertices. Assume that the non-target vertices of G fail independently with given probabilities. The K-terminal reliability of G is defined as the probability that all target vertices in K are connected. Computing K-terminal reliability is #P-complete for chordal graphs, yet solvable in polynomial time for its subclass of interval graphs. While improving both of these results, this work demonstrates that although the problem remains #P-complete when restricted to directed path graphs, a further restriction to rooted directed path graphs yields a polynomial time solution.

The induced path number $$\rho (G)$$?(G) of a graph G is defined as the minimum number of subsets into which the vertex set of G can be partitioned so that each subset induces a path. A product Nordhaus---Gaddum-type result is a bound on the product of a parameter of a graph and its complement. Hattingh et al. (Util Math 94:275---285, 2014) showed that if G is a graph of order n, then $$\lceil \frac{n}{4} \rceil \le \rho (G) \rho (\overline{G}) \le n \lceil \frac{n}{2} \rceil $$?n4?≤?(G)?(G¯)≤n?n2?, where these bounds are best possible. It was also noted that the upper bound is achieved when either G or $$\overline{G}$$G¯ is a graph consisting of n isolated vertices. In this paper, we determine best possible upper and lower bounds for $$\rho (G) \rho (\overline{G})$$?(G)?(G¯) when either both G and $$\overline{G}$$G¯ are connected or neither G nor $$\overline{G}$$G¯ has isolated vertices.

An ( i , j , k ) -path is a path on three vertices u , v and w in this order with d e g ( u ) ? i , d e g ( v ) ? j , and d e g ( w ) ? k . In this paper, we prove that every connected plane graph of girth 4 and minimum degree at least 2 has at least one of the following: a ( 2 , ∞ , 2 ) -path, a ( 2 , 7 , 3 ) -path, a ( 3 , 5 , 3 ) -path, a ( 4 , 2 , 5 ) -path, or a ( 4 , 3 , 4 ) -path. Moreover, no parameter of this description can be improved. Our result supplements recent results concerning the existence of specific 3-paths in plane graphs.

For a graph G and a set H of connected graphs, G is said to be H -free if G does not contain any member of H as an induced subgraph. We let G 2 ( H ) denote the set of all 2-connected H -free graphs. Fujisawa et al. (2013) characterized sets H of connected graphs such that | H | ≤ 3 and G 2 ( H ) is finite. In this paper, we extend their result and characterize sets H of connected graphs such that | H | ≤ 4 and G 2 ( H ) is finite.

The hypercube network is one of the most popular interconnection networks since it has simple structure and is easy to implement. The folded hypercube is an important variation of the hypercube. Interconnection networks play a major role in the performance of distributed memory multiprocessors and the one primary concern for choosing an appropriate interconnection network is the graph embedding ability. A graph embedding of a guest graph G into a host graph H is an injective map on the vertices such that each edge of G is mapped into a path of H . The wirelength of this embedding is defined to be the sum of the lengths of the paths corresponding to the edges of G . In this paper we embed hypercube and folded hypercube onto Cartesian product of trees such as 1-rooted complete binary tree and path, sibling tree and path to minimize the wirelength.

In this paper, we study a variant of the p-median problem on block graphs G in which the p-median is asked to be connected, and this problem is called the connected p-median problem. We first show that the connected p-median problem is NP-hard on block graphs with multiple edge weights. Then, we propose an O(n)-time algorithm for solving the problem on unit-edge-weighted block graphs, where n is the number of vertices in G.

Given an edge-weighted graph G and two distinct vertices s and t of G, the next-to-shortest path problem asks for a path from s to t of minimum length among all paths from s to t except the shortest ones. In this article, we consider the version where G is directed and all edge weights are positive. Some properties of the requested path are derived when G is an arbitrary digraph. In addition, if G is planar, an On3-time algorithm is proposed, where n is the number of vertices of G. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 653, 205-211 2015

A bipartite graph G = ( L , R ; E ) with at least one edge is said to be identifiable if for every vertex v ? L , the subgraph induced by its non-neighbors has a matching of cardinality | L | - 1 . This definition arises in the context of low-rank matrix factorization and is motivated by signal processing applications. An ? -subgraph of a bipartite graph G = ( L , R ; E ) is an induced subgraph of G obtained by deleting from it some vertices in L together with all their neighbors. The Identifiable Subgraph problem is the problem of determining whether a given bipartite graph G = ( L , R ; E ) contains an identifiable ? -subgraph. While the problem of finding a smallest set J ? L that induces an identifiable ? -subgraph of G is NP-hard and also APX-hard, the complexity of the identifiable subgraph problem is still open.In this paper, we introduce and study the k -bounded Identifiable Subgraph problem. This is the variant of the Identifiable Subgraph problem in which the input bipartite graphs G = ( L , R ; E ) are restricted to have the maximum degree of vertices in R bounded by k . We show that for k ? 3 , the k -bounded Identifiable Subgraph problem is as hard as the general case, while it becomes solvable in linear time for k ? 2 . Our proof is based on the notion of strongly cyclic graphs, that is, multigraphs with at least one edge such that for every vertex v , no connected component of the graph obtained by deleting v is a tree. We show that a bipartite graph G = ( L , R ; E ) with maximum degree of vertices in R bounded by 2 is a no instance to the Identifiable Subgraph problem if and only if a multigraph naturally associated to it does not contain any strongly cyclic subgraph, and characterize such graphs in terms of finitely many minimal forbidden topological minors.

For a graph $G$, the \emph{$r$-bootstrap percolation} process can be described as follows: Start with an initial set $A$ of "infected'' vertices. Infect any vertex with at least $r$ infected neighbours, and continue this process until no new vertices can be infected. $A$ is said to \emph{percolate in $G$} if eventually all the vertices of $G$ are infected. $A$ is a \emph{minimal percolating set} in $G$ if $A$ percolates in $G$ and no proper subset of $A$ percolates in $G$. An induced path, $P$, in a hypercube $Q_n$ is maximal if no induced path in $Q_n$ properly contains $P$. Induced paths in hypercubes are also called snakes. We study the relationship between maximal snakes and minimal percolating sets (under 2-bootstrap percolation) in hypercubes. In particular, we show that every maximal snake contains a minimal percolating set, and that every minimal percolating set is contained in a maximal snake.

Let G=(V,E) be a graph of order n and let B(D) be the set of vertices in V∖D that have a neighbor in the vertex set D. The differential of D is defined as ∂(D)=|B(D)|−|D| and the differential of a graph G, written ∂(G), is equal to max⁡{∂(D):D⊆V}. If G is connected and n≥3, ∂(G)≥n/5 is known. This immediately leads to a linear vertex kernel result (in the terminology of parameterized complexity) for the problem of deciding whether ∂(G)≥k, taking k as the parameter. We then establish a new combinatorial result which establishes that ∂(G)≥n/4 if G is a connected graph of order n≥6 and if G contains no induced path of five vertices whose midpoint is a cut vertex and whose endpoints have degree one. This technical combinatorial theorem can be used to derive an even smaller linear vertex kernel for general graphs. Also, we show that the related maximization problem allows for a polynomial-time factor-14 approximation algorithm.

SUMMARY Given an edge-weighted tree with n vertices and a positive integer L, the length-constrained maximum-density path problem is to find a path of length at least L with maximum density in the tree. The density of a path is the sum of the weights of the edges in the path divided by the number of edges in the path. We present an O(n) time algorithm for the problem. The previously known algorithms run in O(nL )o rO(nlogn) time.

We show that for several pattern graphs on four vertices (e.g., \(C_4\)), their induced copies in host graphs with n vertices and no clique on \(k+1\) vertices can be deterministically detected in time \(\tilde{O}(n^{\omega }k^{\mu }+n^2k^2),\) where \(\tilde{O}(f)\) stands for \(O(f (\log f)^c )\) for some constant c, and \(\mu \approx 0.46530\). The aforementioned pattern graphs have a pair of non-adjacent vertices whose neighborhoods are equal. By considering dual graphs, in the same asymptotic time, we can also detect four vertex pattern graphs, that have an adjacent pair of vertices with the same neighbors among the remaining vertices (e.g., \(K_4\)), in host graphs with n vertices and no independent set on \(k+1\) vertices.

It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on t vertices, for fixed t. We propose an algorithm that, given a 3-colorable graph without an induced path on t vertices, computes a coloring with \(\max \left\{ 5,2\left\lceil \frac{t-1}{2}\right\rceil -2\right\} \) many colors. If the input graph is triangle-free, we only need \(\max \left\{ 4,\left\lceil \frac{t-1}{2}\right\rceil +1\right\} \) many colors. The running time of our algorithm is \(O((3^{t-2}+t^2)m+n)\) if the input graph has n vertices and m edges.

Dirac showed that in a -connected graph there is a path through all the k vertices. The k-path-connectivity of a graph G, which is a generalization of Dirac's notion, was introduced by Hager in 1986. Denote by the lexicographic product of two graphs G and H. In this paper, we prove that for any two connected graphs G and H. Moreover, the bound is sharp. We also derive an upper bound of , that is, .

Let G be a non-trivial, simple, finite, connected and undirected graph of order n and size m. An induced acyclic graphoidal decomposition (IAGD) of G is a collection ψ of non-trivial and internally disjoint induced paths in G such that each edge of G lies in exactly one path of ψ. For a labeling f : V → {1, 2, 3, . . . ,n}, let ↑ Gf be the directed graph obtained by orienting the edges uv of G from u to v, provided f(u) < f(v). If the set ψf of all maximal directed induced paths in ↑ Gf with directions ignored is an induced path decomposition of G, then f is called an induced graphoidal labeling of G and G is called an induced label graphoidal graph. The number ηil = min{|ψf| : f is an induced graphoidal labeling of G} is called the induced label graphoidal decomposition number of G. In this paper we introduce and study the concept of induced graphoidal labeling as an extension of graphoidal labeling.

We consider the class of trees for which all vertices of degree at least 3 lie on a single induced path of the tree. For such trees, a new superposition principle is proposed to generate all possible ordered multiplicity lists for the eigenvalues of symmetric (Hermitian) matrices whose graph is such a tree. It is shown that no multiplicity lists other than these can occur and that for two subclasses all such lists do occur. Important contrasts with trees outside the class are given, and it is shown that several prior conjectures about multiplicity lists, including the Degree Conjecture, follow from our superposition principle.

The problem of counting maximal independent sets is #P-complete for chordal graphs but solvable in polynomial time for its subclass of interval graphs. This work improves upon both of these results by showing that the problem remains #P-complete when restricted to directed path graphs but that a further restriction to rooted directed path graphs admits a polynomial time solution.

It is known that the set of all simple graphs is not well-quasi-ordered by the induced subgraph relation, i.e. it contains infinite antichains (sets of incomparable elements) with respect to this relation. However, some particular graph classes are well-quasi-ordered by induced subgraphs. Moreover, some of them are well-quasi-ordered by a stronger relation called labelled induced subgraphs. In this paper, we conjecture that a hereditary class X which is well-quasi-ordered by the induced subgraph relation is also well-quasi-ordered by the labelled induced subgraph relation if and only if X is defined by finitely many minimal forbidden induced subgraphs. We verify this conjecture for a variety of hereditary classes that are known to be well-quasi-ordered by induced subgraphs and prove a number of new results supporting the conjecture.

The Erd?s-Hajnal conjecture states that for every graph H, there exists a constant ?(H)>0, such that if a graph G has no induced subgraph isomorphic to H, then G contains a clique or a stable set of size at least |V (G)|?(H). This conjecture is still open. We consider a variant of the conjecture, where instead of excluding H as an induced subgraph, both H and Hc are excluded. We prove this modified conjecture for the case when H is the five-edge path. Our second main result is an asymmetric version of this: we prove that for every graph G such that G contains no induced six-edge path, and Gc contains no induced four-edge path, G contains a polynomial-size clique or stable set.

Given a graph G, and two vertex sets S and T of size k each, a many-to-many k-disjoint path cover of G joining S and T is a collection of k disjoint paths between S and T that cover every vertex of G. It is classified as paired if each vertex of S must be joined to a designated vertex of T, or unpaired if there is no such constraint. In this article, we first present a necessary and sufficient condition for the cube of a connected graph to have a paired 2-disjoint path cover. Then, a corresponding condition for the unpaired type of 2-disjoint path cover problem is immediately derived. It is also shown that these results can easily be extended to determine if the cube of a connected graph has a hamiltonian path from a given vertex to another vertex that passes through a prescribed edge.

Shortest path query is an important problem and has been well studied in static graphs. However, in practice, the costs of edges in graphs always change over time. We call such graphs as time-dependent graphs. In this paper, we study how to find a cost-optimal path with time constraint in time-dependent graphs. Most existing works regarding the Time-Dependent Shortest Path (TDSP) problem focus on finding a shortest path with the minimum travel time. All these works are based on the following fact: the earliest arrival time at a vertex v can be derived from the earliest arrival time at v 's neighbors. Unfortunately, this fact does not hold for our problem. In this paper, we propose a novel algorithm to compute a cost-optimal path with time constraint in time-dependent graphs. We show that the time and space complexities of our algorithm are O ( kn log n + mk ) and O (( n + m ) k ) respectively. We confirm the effectiveness and efficiency of our algorithm through conducting experiments on real datasets with synthetic cost.

The snake-in-the-box problem asks for the maximum length of a chordless path (also called snake) in the $$n$$n-cube. A computer-aided approach for classifying long snakes in the $$n$$n-cube is here developed. A recursive construction and isomorph rejection via canonical augmentation form the core of the approach. The snake-in-the box problem has earlier been solved for $$n\le 7$$n≤7; that work is here extended by showing that the longest snake in the 8-cube has 98 edges.

For an integer k>=1, a graph G is k-colorable if there exists a mapping c:V"G->{1,...,k} such that c(u) c(v) whenever u and v are two adjacent vertices. For a fixed integer k>=1, the k-Coloring problem is that of testing whether a given graph is k-colorable. The girth of a graph G is the length of a shortest cycle in G. For any fixed g>=4 we determine a lower bound @?(g), such that every graph with girth at least g and with no induced path on @?(g) vertices is 3-colorable. We also show that for all fixed integers k,@?>=1, thek-Coloring problem can be solved in polynomial time for graphs with no induced cycle on four vertices and no induced path on @? vertices. As a consequence, for all fixed integers k,@?>=1 and g>=5, the k-Coloring problem can be solved in polynomial time for graphs with girth at least g and with no induced path on @? vertices. This result is best possible, as we prove the existence of an integer @?^*, such that already 4-Coloring is NP-complete for graphs with girth 4 and with no induced path on @?^* vertices.

Let us say two (simple) graphs G,G^' are degree-equivalent if they have the same vertex set, and for every vertex, its degrees in G and in G^' are equal. In the early 1980's, S.B. Rao made the conjecture that in any infinite set of graphs, there exist two of them, say G and H, such that H is isomorphic to an induced subgraph of some graph that is degree-equivalent to G. We prove this conjecture.

An induced matching of a graph G is a set M of edges of G such that every two vertices of G that are incident with distinct edges in M have distance at least 2 in G. The maximum number of edges in an induced matching of G is the induced matching number @n"s(G) of G. In contrast to ordinary matchings, induced matchings in graphs are algorithmically difficult. Next to hardness results and efficient algorithms for restricted graph classes, lower bounds are therefore of interest. We show that if G is a connected graph of order n(G), maximum degree at most 3, girth at least 6, and without a cycle of length 7, then @n"s(G)>=n(G)-15, and we characterize the graphs achieving equality in this lower bound.

International audience; Cai and Yang initiated the systematic parameterized complexity study of the following set of problems around Eulerian graphs. For a given graph G and integer k, the task is to decide if G contains a (connected) subgraph with k vertices (edges) with all vertices of even (odd) degrees. They succeed to establish the parameterized complexity of all cases except two, when we ask about - a connected k-edge subgraph with all vertices of odd degrees, the problem known as k-Edge Connected Odd Subgraph; and - a connected k- vertex induced subgraph with all vertices of even degrees, the problem known as k-Vertex Eulerian Subgraph. We resolve both open problems and thus complete the characterization of even/odd subgraph problems from parameterized complexity perspective. We show that k-Edge Connected Odd Subgraph is FPT and that k-Vertex Eulerian Subgraph is W[1]-hard. Our FPT algorithm is based on a novel combinatorial result on the treewidth of minimal connected odd graphs with even amount of edges.

Let G be a connected simple graph, let X⊆V (G) and let f be a mapping from X to the set of integers. When X is an independent set, Frank and Gyarfas, and independently, Kaneko and Yoshimoto gave a necessary and sufficient condition for the existence of spanning tree T in G such that d T (x) for all x ? X, where d T (x) is the degree of x and T. In this paper, we extend this result to the case where the subgraph induced by X has no induced path of order four, and prove that there exists a spanning tree T in G such that d T (x) ? f(x) for all x ? X if and only if for any nonempty subset S ⊆ X, |N G (S) ? S| ? f(S) + 2|S| ? ? G (S) ?, where ? G (S) is the number of components of the subgraph induced by S.

A subset S of vertices in a graph G=(V,E) is a connected dominating set of G if every vertex of V@?S is adjacent to a vertex in S and the subgraph induced by S is connected. The minimum cardinality of a connected dominating set of G is the connected domination number @c"c(G). The girth g(G) is the length of a shortest cycle in G. We show that if G is a connected graph that contains at least one cycle, then @c"c(G)>=g(G)-2, and we characterize the graphs obtaining equality in this bound. We also establish various upper bounds on the connected domination number of a graph, as well as Nordhaus-Gaddum type results.

International audience; This paper introduces the problem of identifying vertices of a graph using paths. An identifying path cover of a graph G is a set P of paths such that each vertex belongs to a path of P, and for each pair u, v of vertices, there is a path of P which includes exactly one of u, v. This new notion is related to a large number of other identification problems in graphs and hypergraphs. We study the identifying path cover problem under both combinatorial and algorithmic points of view. In particular, we derive the optimal size of an identifying path cover for paths, cycles and hypercubes, and give upper bounds for trees. We give lower and upper bounds on the minimum size of an identifying path cover for general graphs, and discuss their tightness. In particular, we show that any connected graph G has an identifying path cover of size at most $\lceil 2n/3\rceil+5$. We then study the computational complexity of the associated optimization problem, in particular we show that when the length of the paths is asked to be of bounded value, the problem is APX-complete.

In 1984, Fan gave a sufficient condition involving maximum degree of every pair of vertices at distance two for a graph to be Hamiltonian. Motivated by Fan's result, we say that an induced subgraph $H$ of a graph $G$ is $f$-heavy if for every pair of vertices $u,v\in V(H)$, $d_{H}(u,v)=2$ implies that $\max\{d(u),d(v)\}\geq n/2$. For a given graph $R$, $G$ is called $R$-$f$-heavy if every induced subgraph of $G$ isomorphic to $R$ is $f$-heavy. For a family $\mathcal{R}$ of graphs, $G$ is $\mathcal{R}$-$f$-\emph{heavy} if $G$ is $R$-$f$-heavy for every $R\in \mathcal{R}$. In this note we show that every 2-connected graph $G$ has a Hamilton cycle if $G$ is $\{K_{1,3},P_7,D\}$-$f$-heavy or $\{K_{1,3},P_7,H\}$-$f$-heavy, where $D$ is the deer and $H$ is the hourglass. Our result is a common generalization of previous theorems of Broersma et al. and Fan on Hamiltonicity of 2-connected graphs., 8 pages, 1 figure

Let be the class of all graphs with no induced four-edge path or four-edge antipath. Hayward and Nastos [6] conjectured that every prime graph in not isomorphic to the cycle of length five is either a split graph or contains a certain useful arrangement of simplicial and antisimplicial vertices. In this article, we give a counterexample to their conjecture, and prove a slightly weaker version. Additionally, applying a result of the first author and Seymour [1] we give a short proof of Fouquet's result [3] on the structure of the subclass of bull-free graphs contained in .

When G is a graph with average degree greater than k − 2 , Erdős and Gallai proved that G contains a path on k vertices. Erdős and Sos conjectured that under the same condition, G should contain every tree on k vertices. Several results based upon the number of vertices in G have been proved including the special cases where G has exactly k vertices (Zhou), k + 1 vertices (Slater, Teo and Yap), k + 2 vertices (Woźniak) and k + 3 vertices (Tiner). To strengthen these results, we will prove that the Erdős-Sos conjecture holds when the graph G contains no path with k + 4 vertices (no restriction is imposed on the number of vertices of G ).

We consider undirected graphs without loops or multiple edges. If a and b are vertices in a graph Γ, then d(a, b) denotes the distance between a and b, and Γi(a) denotes the subgraph of Γ induced by the set of vertices of Γ that are a distance of i away from a. The subgraph Γ1(a) is called the neighborhood of a and is denoted by [a]. By a ⊥ we denote the subgraph that is the ball of radius 1 centered at a. Γ is called a regular graph of degree k if [a] contains precisely k vertices for any vertex a in Γ. A graph Γ is – ≤

Given a pattern graph H with l edges, and a host graph G guaranteed to contain at most one occurrence of a subgraph isomorphic to H , we show that the time complexity of the problem of finding such an occurrence if any in G as well as that of the decision version of the problem are within a multiplicative factor O l of the time complexity for the corresponding problem in the general case, when G may contain several occurrences of H . It follows that for pattern graphs of constant size, the aforementioned uniqueness guarantee cannot yield any asymptotic speed up. We also derive analogous results with the analogous multiplicative factor linear in the number of vertices of H in the induced case when occurrences of induced subgraphs of G isomorphic to H are sought.

An edge ordering of a graph G is an injection f : E → R , the set of real numbers. A path in G for which the edge ordering f increases along its edge sequence is called an f -ascent; an f -ascent is maximal if it is not contained in a longer f -ascent. The depression of G is the smallest integer k such that any edge ordering f has a maximal f -ascent of length at most k . We characterize the class of graphs with depression three and without adjacent vertices of degree three or higher.

The snake-in-the-box problem is concerned with finding a longest induced path in a hypercube $$Q_n$$Qn. Similarly, the coil-in-the-box problem is concerned with finding a longest induced cycle in $$Q_n$$Qn. We consider a generalization of these problems that considers paths and cycles where each pair of vertices at distance at least $$k$$k in the path or cycle are also at distance at least $$k$$k in $$Q_n$$Qn. We call these paths $$k$$k-snakes and the cycles $$k$$k-coils. The $$k$$k-coils have also been called circuit codes. By optimizing an exhaustive search algorithm, we find 13 new longest $$k$$k-coils, 21 new longest $$k$$k-snakes and verify that some of them are optimal. By optimizing an algorithm by Paterson and Tuliani to find single-track circuit codes, we additionally find another 8 new longest $$k$$k-coils. Using these $$k$$k-coils with some basic backtracking, we find 18 new longest $$k$$k-snakes.

A decomposition of a graph is a collection of edge-disjoint subgraphs of such that every edge of belongs to exactly one . If each is a path or a cycle in , then is called a path decomposition of . If each is a path in , then is called an acyclic path decomposition of . The minimum cardinality of a path decomposition (acyclic path decomposition) of is called the path decomposition number (acyclic path decomposition number) of and is denoted by () (()). In this paper we initiate a study of the parameter and determine the value of for some standard graphs. Further, we obtain some bounds for and characterize graphs attaining the bounds. We also prove that the difference between the parameters and can be made arbitrarily large.

Let I G ( x , y ) and J G ( x , y ) be the geodesic and induced path intervals between x and y in a connected graph G , respectively. The following three betweenness axioms are considered for a set V and R : V × V → 2 V : (i) x ∈ R ( u , y ) , y ∈ R ( x , v ) , x ≠ y , | R ( u , v ) | > 2 ⇒ x ∈ R ( u , v ) ; (ii) x ∈ R ( u , v ) ⇒ R ( u , x ) ∩ R ( x , v ) = { x } ; (iii) x ∈ R ( u , y ) , y ∈ R ( x , v ) , x ≠ y ⇒ x ∈ R ( u , v ) . We characterize the class of graphs for which I G satisfies (i), the class for which J G satisfies (ii) and the class for which I G or J G satisfies (iii). The characterization is given in terms of forbidden induced subgraphs. It turns out that the class of graphs for which I G satisfies (i) is a proper subclass of distance hereditary graphs and the class for which J G satisfies (ii) is a proper superclass of distance hereditary graphs. We also give an axiomatic characterization of chordal and Ptolemaic graphs.

In 1966, Gallai conjectured that for any simple, connected graph G having n vertices, there is a path-decomposition of G having at most paths. In this article, we show that for any simple graph G having girth , there is a path-decomposition of G having at most paths, where is the number of vertices of odd degree in G and is the number of nonisolated vertices of even degree in G.

The Path Partition Conjecture (PPC) states that if G is any graph and (λ1, λ2) any pair of positive integers such that G has no path with more than λ1 + λ2 vertices, then there exists a partition (V1, V2) of the vertex set of G such that Vi has no path with more than λi vertices, i = 1, 2. We present a brief history of the PPC, discuss its relation to other conjectures and survey results on the PPC that have appeared in the literature since its first formulation in 1981.

Many recognition problems for special classes of graphs and cycles can be reduced to finding and listing induced paths and cycles in a graph. We design algorithms to list all P"3's in O(m^1^.^5+p"3(G)) time, and for k>=4 all P"k's in O(n^k^-^1+p"k(G)+k@?c"k(G)) time, where p"k(G), respectively, c"k(G), are the number of P"k's, respectively, C"k's, of a graph G. We also provide an algorithm to find a P"k, k>=5, in time O(k!!@?m^(^k^-^1^)^/^2) if k is odd, and O(k!!@?nm^(^k^/^2^)^-^1) if k is even. As applications of our findings, we give algorithms to recognize quasi-triangulated graphs and brittle graphs. Our algorithms' time bounds are incomparable with previously known algorithms.

In this paper it is proved that there are constants 0 c 2 c 1 such that the number of (labeled) n -vertex graphs of diameter d is ( 1 + o ( 1 ) ) d − 2 2 n ( d − 1 ) 3 n − d + 1 2 n − d + 1 2 whenever n → ∞ and 3 ≤ d ≤ n − c 1 log n , where n ( d − 1 ) = n ( n − 1 ) … ( n − d + 2 ) . A typical graph of diameter d consists of a combination of an induced path of length d and a highly connected block of size n − d + 3 . In the case d > n − c 2 log n the typical graph has a completely different snakelike structure. The number of n -vertex graphs of diameter d is ( 1 + o ( 1 ) ) 1 2 n ( d + 1 ) 3 n − d − 1 d n − d − 1 whenever n → ∞ and d > n − c 2 log n .