			Home About us Contact

Graph H (graph + h)

Distribution by Scientific Domains

Mathematics and Statistics	100%

Selected Abstracts

Forbidden induced bipartite graphs

JOURNAL OF GRAPH THEORY, Issue 3 2009
Peter Allen
Abstract Given a fixed bipartite graph H, we study the asymptotic speed of growth of the number of bipartite graphs on n vertices which do not contain an induced copy of H. Whenever H contains either a cycle or the bipartite complement of a cycle, the speed of growth is . For every other bipartite graph except the path on seven vertices, we are able to find both upper and lower bounds of the form . In many cases we are able to determine the correct value of c. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 219,241, 2009 [source]

On k -detour subgraphs of hypercubes

JOURNAL OF GRAPH THEORY, Issue 1 2008
Nana Arizumi
Abstract A spanning subgraph G of a graph H is a k - detour subgraph of H if for each pair of vertices , the distance, , between x and y in G exceeds that in H by at most k. Such subgraphs sometimes also are called additive spanners. In this article, we study k -detour subgraphs of the n -dimensional cube, , with few edges or with moderate maximum degree. Let denote the minimum possible maximum degree of a k -detour subgraph of . The main result is that for every and On the other hand, for each fixed even and large n, there exists a k -detour subgraph of with average degree at most . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 55,64, 2008 [source]

The minimum degree of Ramsey-minimal graphs

JOURNAL OF GRAPH THEORY, Issue 2 2007
Jacob Fox
Abstract We write H,,,G if every 2-coloring of the edges of graph H contains a monochromatic copy of graph G. A graph H is G - minimal if H,,,G, but for every proper subgraph H, of H, H,,,,,G. We define s(G) to be the minimum s such that there exists a G -minimal graph with a vertex of degree s. We prove that s(Kk),=,(k,,,1)2 and s(Ka,b),=,2 min(a,b),,,1. We also pose several related open problems. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 167,177, 2007 [source]

A constructive approach for the lower bounds on the Ramsey numbers R (s, t)

JOURNAL OF GRAPH THEORY, Issue 3 2004
Xu Xiaodong
Abstract Graph G is a (k,,p)-graph if G does not contain a complete graph on k vertices Kk, nor an independent set of order p. Given a (k,,p)-graph G and a (k,,q)-graph H, such that G and H contain an induced subgraph isomorphic to some Kk,1 -free graph M, we construct a (k,,p,+,q,,,1)-graph on n(G),+,n(H),+,n(M) vertices. This implies that R,(k,,p,+,q,,,1),,,R,(k,,p),+,R,(k,,q),+,n(M),,,1, where R,(s,,t) is the classical two-color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R,(s,,t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R,(4,,15) , 153, R,(6,,7) , 111, R,(6,,11) , 253, R,(7,,12) , 416, and R,(8,,13) , 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231,239, 2004 [source]

On possible counterexamples to Negami's planar cover conjecture

JOURNAL OF GRAPH THEORY, Issue 3 2004
Petr Hlin
Abstract A simple graph H is a cover of a graph G if there exists a mapping , from H onto G such that , maps the neighbors of every vertex , in H bijectively to the neighbors of , (,) in G. Negami conjectured in 1986 that a connected graph has a finite planar cover if and only if it embeds in the projective plane. The conjecture is still open. It follows from the results of Archdeacon, Fellows, Negami, and the first author that the conjecture holds as long as the graph K1,2,2,2 has no finite planar cover. However, those results seem to say little about counterexamples if the conjecture was not true. We show that there are, up to obvious constructions, at most 16 possible counterexamples to Negami's conjecture. Moreover, we exhibit a finite list of sets of graphs such that the set of excluded minors for the property of having finite planar cover is one of the sets in our list. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 183,206, 2004 [source]

Bi-arc graphs and the complexity of list homomorphisms

JOURNAL OF GRAPH THEORY, Issue 1 2003
Tomas Feder
Abstract Given graphs G, H, and lists L(v) , V(H), v , V(G), a list homomorphism of G to H with respect to the lists L is a mapping f : V(G) , V(H) such that uv , E(G) implies f(u)f(v) , E(H), and f(v) , L(v) for all v , V(G). The list homomorphism problem for a fixed graph H asks whether or not an input graph G, together with lists L(v) , V(H), v , V(G), admits a list homomorphism with respect to L. In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP -complete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and H is a circular arc graph, and is NP -complete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called bi-arc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a bi-arc graph, and is NP -complete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 61,80, 2003 [source]

Forcing a Kr minor by high external connectivity

JOURNAL OF GRAPH THEORY, Issue 4 2002
Daniela Kühn
Abstract We investigate the minimal structure a graph H is required to have if H is to force a large complete minor in any graph in which it has high external connectivity. We observe that such graphs H must contain a large binary tree with some small additions, and prove that some canonical instances of this structure are also sufficient to force a large complete minor. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 241,264, 2002; DOI 10.1002/jgt.10026 [source]

Another two graphs with no planar covers

JOURNAL OF GRAPH THEORY, Issue 4 2001
Petr Hlin
Abstract A graph H is a cover of a graph G if there exists a mapping , from V(H) onto V(G) such that , maps the neighbors of every vertex , in H bijectively to the neighbors of ,(,) in G. Negami conjectured in 1986 that a connected graph has a finite planar cover if and only if it embeds in the projective plane. It follows from the results of Archdeacon, Fellows, Negami, and the author that the conjecture holds as long as K1,2,2,2 has no finite planar cover. However, this is still an open question, and K1,2,2,2 is not the only minor-minimal graph in doubt. Let ,,4 (,2) denote the graph obtained from K1,2,2,2 by replacing two vertex-disjoint triangles (four edge-disjoint triangles) not incident with the vertex of degree 6 with cubic vertices. We prove that the graphs ,,4 and ,2 have no planar covers. This fact is used in [P. Hlin,ný, R. Thomas, On possible counterexamples to Negami's planar cover conjecture, 1999 (submitted)] to show that there are, up to obvious constructions, at most 16 possible counterexamples to Negami's conjecture. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 227,242, 2001 [source]

The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases,

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2008
Asaf Levin
Abstract For a fixed pattern graph H, let H -CONTRACTIBILITY denote the problem of deciding whether a given input graph is contractible to H. This paper is part I of our study on the computational complexity of the H -CONTRACTIBILITY problem. We continue a line of research that was started in 1987 by Brouwer and Veldman, and we determine the computational complexity of the H -CONTRACTIBILITY problem for certain classes of pattern graphs. In particular, we pinpoint the complexity for all graphs H with five vertices except for two graphs, whose polynomial time algorithms are presented in part II. Interestingly, in all connected cases that are known to be polynomially solvable, the pattern graph H has a dominating vertex, whereas in all cases that are known to be NP-complete, the pattern graph H does not have a dominating vertex. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008 [source]

The ultracenter and central fringe of a graph

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2001
Gary Chartrand
Abstract The central distance of a central vertex v in a connected graph G with rad G < diam G is the largest nonnegative integer n such that whenever x is a vertex with d(v, x) , n then x is also a central vertex. The subgraph induced by those central vertices of maximum central distance is the ultracenter of G. The subgraph induced by the central vertices having central distance 0 is the central fringe of G. For a given graph G, the smallest order of a connected graph H is determined whose ultracenter is isomorphic to G but whose center is not G. For a given graph F, we determine the smallest order of a connected graph H whose central fringe is isomorphic to G but whose center is not G. © 2001 John Wiley & Sons, Inc. [source]

Proof of a tiling conjecture of Komlós

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2003
Ali Shokoufandeh
Abstract A conjecture of Komlós states that for every graph H, there is a constant K such that if G is any n -vertex graph of minimum degree at least (1 , (1/,cr(H)))n, where ,cr(H) denotes the critical chromatic number of H, then G contains an H -matching that covers all but at most K vertices of G. In this paper we prove that the conjecture holds for all sufficiently large values of n. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 180,205, 2003 [source]

Graham's pebbling conjecture on products of cycles

JOURNAL OF GRAPH THEORY, Issue 2 2003
David S. Herscovici
Abstract Chung defined a pebbling move on a graph G to be the removal of two pebbles from one vertex and the addition of one pebble to an adjacent vertex. The pebbling number of a connected graph is the smallest number f(G) such that any distribution of f(G) pebbles on G allows one pebble to be moved to any specified, but arbitrary vertex by a sequence of pebbling moves. Graham conjectured that for any connected graphs G and H, f(G×H), f(G)f(H). We prove Graham's conjecture when G is a cycle for a variety of graphs H, including all cycles. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 141,154, 2003 [source]