Home About us Contact
|
Home About us Contact | ||
|
|
||
N Vertices (n + vertex)
Selected Abstractsd -Regular graphs of acyclic chromatic index at least d+2JOURNAL OF GRAPH THEORY, Issue 3 2010Manu Basavaraju Abstract An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a,(G). It was conjectured by Alon, Sudakov and Zaks (and earlier by Fiamcik) that a,(G),,+2, where ,=,(G) denotes the maximum degree of the graph. Alon et al. also raised the question whether the complete graphs of even order are the only regular graphs which require ,+2 colors to be acyclically edge colored. In this article, using a simple counting argument we observe not only that this is not true, but in fact all d -regular graphs with 2n vertices and d>n, requires at least d+ 2 colors. We also show that a,(Kn, n),n+ 2, when n is odd using a more non-trivial argument. (Here Kn, n denotes the complete bipartite graph with n vertices on each side.) This lower bound for Kn, n can be shown to be tight for some families of complete bipartite graphs and for small values of n. We also infer that for every d, n such that d,5, n,2d+ 3 and dn even, there exist d -regular graphs which require at least d+2-colors to be acyclically edge colored. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 226,230, 2010 [source] Non-rainbow colorings of 3-, 4- and 5-connected plane graphsJOURNAL OF GRAPH THEORY, Issue 2 2010k Dvo Abstract We study vertex-colorings of plane graphs that do not contain a rainbow face, i.e., a face with vertices of mutually distinct colors. If G is a 3 -connected plane graph with n vertices, then the number of colors in such a coloring does not exceed . If G is 4 -connected, then the number of colors is at most , and for n,3(mod8), it is at most . Finally, if G is 5 -connected, then the number of colors is at most . The bounds for 3 -connected and 4 -connected plane graphs are the best possible as we exhibit constructions of graphs with colorings matching the bounds. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 129,145, 2010 [source] Forbidden induced bipartite graphsJOURNAL OF GRAPH THEORY, Issue 3 2009Peter 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] Perfect coloring and linearly ,-bound P6 -free graphsJOURNAL OF GRAPH THEORY, Issue 4 2007S. A. Choudum Abstract We derive decomposition theorems for P6, K1 + P4 -free graphs, P5, K1 + P4 -free graphs and P5, K1 + C4 -free graphs, and deduce linear ,-binding functions for these classes of graphs (here, Pn (Cn) denotes the path (cycle) on n vertices and K1 + G denotes the graph obtained from G by adding a new vertex and joining it with every vertex of G). Using the same techniques, we also obtain an optimal ,-binding function for P5, C4 -free graphs which is an improvement over that given in [J. L. Fouquet, V. Giakoumakis, F. Maire, and H. Thuillier, 1995, Discrete Math, 146, 33,44.]. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 293,306, 2007 [source] The kth Laplacian eigenvalue of a treeJOURNAL OF GRAPH THEORY, Issue 1 2007Ji-Ming Guo Abstract Let ,k(G) be the kth Laplacian eigenvalue of a graph G. It is shown that a tree T with n vertices has and that equality holds if and only if k < n, k|n and T is spanned by k vertex disjoint copies of , the star on vertices. © 2006 Wiley Periodicals, Inc. J Graph Theory [source] How many disjoint 2-edge paths must a cubic graph have?JOURNAL OF GRAPH THEORY, Issue 1 2004Alexander Kelmans Abstract In this paper we show that every simple cubic graph on n vertices has a set of at least ,,n/4,, disjoint 2-edge paths and that this bound is sharp. Our proof provides a polynomial time algorithm for finding such a set in a simple cubic graph. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 57,79, 2003 [source] Almost all graphs with high girth and suitable density have high chromatic numberJOURNAL OF GRAPH THEORY, Issue 4 2001Deryk Osthus Erdös proved that there exist graphs of arbitrarily high girth and arbitrarily high chromatic number. We give a different proof (but also using the probabilistic method) that also yields the following result on the typical asymptotic structure of graphs of high girth: for all ,,,,3 and k , , there exist constants C1 and C2 so that almost all graphs on n vertices and m edges whose girth is greater than , have chromatic number at least k, provided that . © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 220,226, 2001 [source] Minimum multiple message broadcast graphsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2006Hovhannes A. Harutyunyan Abstract Multiple message broadcasting is the process of multiple message dissemination in a communication network in which m messages, originated by one vertex, are transmitted to all vertices of the network. A graph G with n vertices is called a m-message broadcast graph if its broadcast time is the theoretical minimum. Bm(n) is the minimum number of edges in any m-message broadcast graph on n vertices. An m-message minimum broadcast graph is a broadcast graph G on n vertices having Bm(n) edges. This article presents several lower and upper bounds on Bm(n). In particular, it is shown that modified Knödel graphs are m-message broadcast graphs for m , min,log n,,n , 2,log n,. From the Cartesian product of some broadcast graphs we obtain better upper bounds on Bm(n), and in some cases we can prove that Bm(n) = O(n). The exact value of B2(2k) is also established. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(4), 218,224 2006 [source] Approximation algorithms for constructing wavelength routing networksNETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2002Refael Hassin Abstract Consider a requirement graph whose vertices represent customers and an edge represents the need to route a unit of flow between its end vertices along a single path. All these flows are to be routed simultaneously. A solution network consists of a (multi)graph on the same set of vertices, such that it is possible to route simultaneously all of the required flows in such a way that no edge is used more than K times. The SYNTHESIS OF WAVELENGTH ROUTING NETWORK (SWRN) problem is to compute a solution network of a minimum number of edges. This problem has significant importance in the world of fiber-optic networks where a link can carry a limited amount of different wavelengths and one is interested in finding a minimum-cost network such that all the requirements can be carried in the network without changing the wavelength of a path at any of its internal vertices. In this paper, we prove that the SWRN problem is NP-hard for any constant K (K , 2). Then, we assume that GR is a clique with n vertices and we find an "almost" optimal solution network for all values of K (K = o(n)) and present a Min{(K + 1)/2, 2 + 2/(K , 1)}-approximation algorithm for the general case and a 2-approximation algorithm for d -regular graphs. © 2002 Wiley Periodicals, Inc. [source] Robust location problems with pos/neg weights on a treeNETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2001Rainer E. Burkard Abstract In this paper, we consider different aspects of robust 1-median problems on a tree network with uncertain or dynamically changing edge lengths and vertex weights which can also take negative values. The dynamic nature of a parameter is modeled by a linear function of time. A linear algorithm is designed for the absolute dynamic robust 1-median problem on a tree. The dynamic robust deviation 1-median problem on a tree with n vertices is solved in O(n2 ,(n) log n) time, where ,(n) is the inverse Ackermann function. Examples show that both problems do not possess the vertex optimality property. The uncertainty is modeled by given intervals, in which each parameter can take a value randomly. The absolute robust 1-median problem with interval data, where vertex weights might also be negative, can be solved in linear time. The corresponding deviation problem can be solved in O(n2) time. © 2001 John Wiley & Sons, Inc. [source] Minors in random regular graphsRANDOM STRUCTURES AND ALGORITHMS, Issue 4 2009Nikolaos Fountoulakis Abstract We show that there is a constant c so that for fixed r , 3 a.a.s. an r -regular graph on n vertices contains a complete graph on vertices as a minor. This confirms a conjecture of Markström (Ars Combinatoria 70 (2004) 289,295). Since any minor of an r -regular graph on n vertices has at most rn/2 edges, our bound is clearly best possible up to the value of the constant c. As a corollary, we also obtain the likely order of magnitude of the largest complete minor in a random graph Gn,p during the phase transition (i.e., when pn , 1). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source] Uniform random sampling of planar graphs in linear time,RANDOM STRUCTURES AND ALGORITHMS, Issue 4 2009Éric Fusy Abstract This article introduces new algorithms for the uniform random generation of labelled planar graphs. Its principles rely on Boltzmann samplers, as recently developed by Duchon, Flajolet, Louchard, and Schaeffer. It combines the Boltzmann framework, a suitable use of rejection, a new combinatorial bijection found by Fusy, Poulalhon, and Schaeffer, as well as a precise analytic description of the generating functions counting planar graphs, which was recently obtained by Giménez and Noy. This gives rise to an extremely efficient algorithm for the random generation of planar graphs. There is a preprocessing step of some fixed small cost; and the expected time complexity of generation is quadratic for exact-size uniform sampling and linear for uniform approximate-size sampling. This greatly improves on the best previously known time complexity for exact-size uniform sampling of planar graphs with n vertices, which was a little over O(n7). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source] What is the furthest graph from a hereditary property?RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2008Noga Alon Abstract For a graph property P, the edit distance of a graph G from P, denoted EP(G), is the minimum number of edge modifications (additions or deletions) one needs to apply to G to turn it into a graph satisfying P. What is the furthest graph on n vertices from P and what is the largest possible edit distance from P? Denote this maximal distance by ed(n,P). This question is motivated by algorithmic edge-modification problems, in which one wishes to find or approximate the value of EP(G) given an input graph G. A monotone graph property is closed under removal of edges and vertices. Trivially, for any monotone property, the largest edit distance is attained by a complete graph. We show that this is a simple instance of a much broader phenomenon. A hereditary graph property is closed under removal of vertices. We prove that for any hereditary graph property P, a random graph with an edge density that depends on P essentially achieves the maximal distance from P, that is: ed(n,P) = EP(G(n,p(P))) + o(n2) with high probability. The proofs combine several tools, including strengthened versions of the Szemerédi regularity lemma, properties of random graphs and probabilistic arguments. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 [source] A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs,RANDOM STRUCTURES AND ALGORITHMS, Issue 4 2007Surender Baswana Abstract Let G = (V,E) be an undirected weighted graph on |V | = n vertices and |E| = m edges. A t -spanner of the graph G, for any t , 1, is a subgraph (V,ES), ES , E, such that the distance between any pair of vertices in the subgraph is at most t times the distance between them in the graph G. Computing a t -spanner of minimum size (number of edges) has been a widely studied and well-motivated problem in computer science. In this paper we present the first linear time randomized algorithm that computes a t -spanner of a given weighted graph. Moreover, the size of the t -spanner computed essentially matches the worst case lower bound implied by a 43-year old girth lower bound conjecture made independently by Erd,s, Bollobás, and Bondy & Simonovits. Our algorithm uses a novel clustering approach that avoids any distance computation altogether. This feature is somewhat surprising since all the previously existing algorithms employ computation of some sort of local or global distance information, which involves growing either breadth first search trees up to ,(t)-levels or full shortest path trees on a large fraction of vertices. The truly local approach of our algorithm also leads to equally simple and efficient algorithms for computing spanners in other important computational environments like distributed, parallel, and external memory. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007 [source] A simple solution to the k -core problemRANDOM STRUCTURES AND ALGORITHMS, Issue 1-2 2007Svante Janson Abstract We study the k -core of a random (multi)graph on n vertices with a given degree sequence. We let n ,,. Then, under some regularity conditions on the degree sequences, we give conditions on the asymptotic shape of the degree sequence that imply that with high probability the k -core is empty and other conditions that imply that with high probability the k -core is non-empty and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these are the only two possibilities. In particular, we recover the result by Pittel, Spencer, and Wormald (J Combinator Theory 67 (1996), 111,151) on the existence and size of a k -core in G(n,p) and G(n,m), see also Molloy (Random Struct Algor 27 (2005), 124,135) and Cooper (Random Struct Algor 25 (2004), 353,375). Our method is based on the properties of empirical distributions of independent random variables and leads to simple proofs. © 2006 Wiley Periodicals, Inc. Random Struct. Alg.,, 2007 [source] A spectral heuristic for bisecting random graphs,RANDOM STRUCTURES AND ALGORITHMS, Issue 3 2006Amin Coja-OghlanArticle first published online: 27 DEC 200 The minimum bisection problem is to partition the vertices of a graph into two classes of equal size so as to minimize the number of crossing edges. Computing a minimum bisection is NP-hard in the worst case. In this paper we study a spectral heuristic for bisecting random graphs Gn(p,p,) with a planted bisection obtained as follows: partition n vertices into two classes of equal size randomly, and then insert edges inside the two classes with probability p, and edges crossing the partition with probability p independently. If , where c0 is a suitable constant, then with probability 1 , o(1) the heuristic finds a minimum bisection of Gn(p,p,) along with a certificate of optimality. Furthermore, we show that the structure of the set of all minimum bisections of Gn(p,p,) undergoes a phase transition as . The spectral heuristic solves instances in the subcritical, the critical, and the supercritical phases of the phase transition optimally with probability 1 , o(1). These results extend previous work of Boppana Proc. 28th FOCS (1987) 280,285. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 [source] Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraintsRANDOM STRUCTURES AND ALGORITHMS, Issue 4 2003Noga Alon We consider a canonical Ramsey type problem. An edge-coloring of a graph is called m-good if each color appears at most m times at each vertex. Fixing a graph G and a positive integer m, let f(m, G) denote the smallest n such that every m -good edge-coloring of Kn yields a properly edge-colored copy of G, and let g(m, G) denote the smallest n such that every m -good edge-coloring of Kn yields a rainbow copy of G. We give bounds on f(m, G) and g(m, G). For complete graphs G = Kt, we have c1mt2/ln t , f(m, Kt) , c2mt2, and cmt3/ln t , g(m, Kt) , cmt3/ln t, where c1, c2, c, c are absolute constants. We also give bounds on f(m, G) and g(m, G) for general graphs G in terms of degrees in G. In particular, we show that for fixed m and d, and all sufficiently large n compared to m and d, f(m, G) = n for all graphs G with n vertices and maximum degree at most d. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003 [source] On the asymmetry of random regular graphs and random graphsRANDOM STRUCTURES AND ALGORITHMS, Issue 3-4 2002Jeong Han Kim This paper studies the symmetry of random regular graphs and random graphs. Our main result shows that for all 3 , d , n , 4 the random d -regular graph on n vertices almost surely has no nontrivial automorphisms. This answers an open question of N. Wormald [13]. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 216,224, 2002 [source] On the maximum number of Hamiltonian paths in tournamentsRANDOM STRUCTURES AND ALGORITHMS, Issue 3 2001Ilan Adler By using the probabilistic method, we show that the maximum number of directed Hamiltonian paths in a complete directed graph with n vertices is at least (e,o(1)) (n!/2n,1). © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 291,296, 2001 [source] | ||||||||||