Home About us Contact
|
Home About us Contact | ||
|
|
||
Complete Graph (complete + graph)
Selected AbstractsUnavoidable parallel minors of 4-connected graphsJOURNAL OF GRAPH THEORY, Issue 4 2009Carolyn Chun A parallel minor is obtained from a graph by any sequence of edge contractions and parallel edge deletions. We prove that, for any positive integer k, every internally 4-connected graph of sufficiently high order contains a parallel minor isomorphic to a variation of K4,k with a complete graph on the vertices of degree k, the k -partition triple fan with a complete graph on the vertices of degree k, the k -spoke double wheel, the k -spoke double wheel with axle, the (2k+1)-rung Möbius zigzag ladder, the (2k)-rung zigzag ladder, or Kk. We also find the unavoidable parallel minors of 1-, 2-, and 3-connected graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 313-326, 2009 [source] A constructive approach for the lower bounds on the Ramsey numbers R (s, t)JOURNAL OF GRAPH THEORY, Issue 3 2004Xu 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] Independent perfect domination sets in Cayley graphsJOURNAL OF GRAPH THEORY, Issue 4 2001Jaeun Lee In this paper, we show that a Cayley graph for an abelian group has an independent perfect domination set if and only if it is a covering graph of a complete graph. As an application, we show that the hypercube Qn has an independent perfect domination set if and only if Qn is a regular covering of the complete graph Kn+1 if and only if n,=,2m,,,1 for some natural number m. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 213,219, 2001 [source] Implementing molecular connectivity theory, a basic tool in modeling drugsJOURNAL OF PHARMACEUTICAL SCIENCES, Issue 8 2007Lionello Pogliani Abstract The concepts of chain graph, general graph, and complete graph have been used to implement the graph framework of molecular connectivity (MC) theory. Some concepts of this theory have been addressed using "external" theoretical concepts belonging mostly to quantum or structural chemistry, with no direct counterpart in graph theory. Thus, while the concept of chain graph can be used to tackle the cis-trans isomerism problem, the concept of pseudograph, or general graph can be used to tackle the description of the sigma -, pi -, and nonbonding n -electrons. The concept of complete graph can instead be used to tackle the electron core problem of the atoms of a molecule. Graph concepts can also be used to tackle the problem of the hydrogen contribution in hydrogen depleted graphs, which are encoded by the aid of a perturbation parameter, which differentiates between compounds with similar hydrogen-suppressed chemical graphs, like the graphs of CH3F and BH2F. These concepts have allowed redesign of a central parameter of MC theory, the valence delta, giving MC indices with improved model quality as exemplified here with different properties for each treated topic. © 2007 Wiley-Liss, Inc. and the American Pharmacists Association J Pharm Sci 96:1856,1871, 2007 [source] Vertex disjoint routings of cycles over toriNETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2007Jean-Claude Bermond Abstract We study the problem of designing a survivable WDM network based on covering the communication requests with subnetworks that are protected independently from each other. We consider here the case when the physical network is T(n), a torus of size n by n, the subnetworks are cycles and the communication scheme is all-to-all or total exchange (where all pairs of vertices communicate). We will represent the communication requests by a logical graph: a complete graph for the scheme of all-to-all. This problem can be modeled as follows: find a cycle partition or covering of the request edges of K, such that for each cycle in the partition, its request edges can be routed in the physical network T(n) by a set of vertex disjoint paths (equivalently, the routings with the request cycle form an elementary cycle in T(n)). Let the load of an edge of the WDM network be the number of paths associated with the requests using the edge. The cost of the network depends on the total load (the cost of transmission) and the maximum load (the cost of equipment). To minimize these costs, we will search for an optimal (or quasi optimal) routing satisfying the following two conditions: (a) each request edge is routed by a shortest path over T(n), and (b) the load of each physical edge resulting from the routing of all cycles of S is uniform or quasi uniform. In this article, we find a covering or partition of the request edges of K into cycles with an associated optimal or quasi optimal routing such that either (1) the number of cycles of the covering is minimum, or (2) the cycles have size 3 or 4. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(3), 217,225 2007 [source] A network flow algorithm to minimize beam-on time for unconstrained multileaf collimator problems in cancer radiation therapyNETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2005Ravindra K. Ahuja Abstract In this article, we study the modulation of intensity matrices arising in cancer radiation therapy using multileaf collimators. This problem can be formulated by decomposing a given m × n integer matrix into a positive linear combination of (0, 1) matrices with the strict consecutive 1's property in rows. We consider a special case in which no technical constraints have to be taken into account. In this situation, the rows of the intensity matrix are independent of each other and the problem is equivalent to decomposing m intensity rows,independent of each other,into positive linear combinations of (0, 1) rows with the consecutive 1's property. We demonstrate that this problem can be transformed into a minimum cost flow problem in a directed network that has the following special structures: (1) the network is acyclic; (2) it is a complete graph (that is, there is an arc (i, j) whenever i < j); (3) each arc cost is 1; and (4) each arc is uncapacitated (that is, it has infinite capacity). We show that using this special structure, the minimum cost flow problem can be solved in O(n) time. Because we need to solve m such problems, the total running time of our algorithm is O(nm), which is an optimal algorithm to decompose a given m × n integer matrix into a positive linear combination of (0, 1) matrices. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(1), 36,41 2005 [source] Super edge- and point-connectivities of the Cartesian product of regular graphsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2002Bih-Sheue Shieh Abstract We prove that the Cartesian product of two regular graphs with maximum edge (respectively, point-)-connectivity is super edge (respectively, point-)-connected except for the case K2 × Kn, n , 2 (respectively, n , 4), where Kn is a complete graph of order n. Using these results, certain classes of networks which are recursively defined by the Cartesian product can be simply shown to possess super edge-connectivity and super point-connectivity. © 2002 Wiley Periodicals, Inc. [source] Weight of a link in a shortest path tree and the Dedekind Eta functionRANDOM STRUCTURES AND ALGORITHMS, Issue 3 2010Piet Van Mieghem Abstract The weight of a randomly chosen link in the shortest path tree on the complete graph with exponential i.i.d. link weights is studied. The corresponding exact probability generating function and the asymptotic law are derived. As a remarkable coincidence, this asymptotic law is precisely the same as the distribution of the cost of one "job" in the random assignment problem. We also show that the asymptotic (scaled) maximum interattachment time to that shortest path tree, which is a uniform recursive tree, equals the square of the Dedekind Eta function, a central function in modular forms, elliptic functions, and the theory of partitions. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010 [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] 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] Large-deviations/thermodynamic approach to percolation on the complete graphRANDOM STRUCTURES AND ALGORITHMS, Issue 3 2007Marek Biskup Abstract We present a large-deviations/thermodynamic approach to the classic problem of percolation on the complete graph. Specifically, we determine the large-deviation rate function for the probability that the giant component occupies a fixed fraction of the graph while all other components are "small." One consequence is an immediate derivation of the "cavity" formula for the fraction of vertices in the giant component. As a byproduct of our analysis we compute the large-deviation rate functions for the probability of the event that the random graph is connected, the event that it contains no cycles and the event that it contains only small components. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007 [source] Complete graph conjecture for inner-core electrons: Homogeneous index caseJOURNAL OF COMPUTATIONAL CHEMISTRY, Issue 9 2003Lionello Pogliani Abstract The complete graph conjecture that encodes the inner-core electrons of atoms with principal quantum number n , 2 with complete graphs, and especially with odd complete graphs, is discussed. This conjecture is used to derive new values for the molecular connectivity and pseudoconnectivity basis indices of hydrogen-suppressed chemical pseudographs. For atoms with n = 2 the new values derived with this conjecture are coincident with the old ones. The modeling ability of the new homogeneous basis indices, and of the higher-order terms, is tested and compared with previous modeling studies, which are centered on basis indices that are either based on quantum concepts or partially based on this new conjecture for the inner-core electrons. Two similar algorithms have been proposed with this conjecture, and they parallel the two "quantum" algorithms put forward by molecular connectivity for atoms with n > 2. Nine properties of five classes of compounds have been tested: the molecular polarizabilities of a class of organic compounds, the dipole moment, molar refraction, boiling points, ionization energies, and parachor of a series of halomethanes, the lattice enthalpy of metal halides, the rates of hydrogen abstraction of chlorofluorocarbons, and the pED50 of phenylalkylamines. The two tested algorithms based on the odd complete graph conjecture give rise to a highly interesting model of the nine properties, and three of them can even be modeled by the same set of basis indices. Interesting is the role of some basis indices all along the model. © 2003 Wiley Periodicals, Inc. J Comput Chem 9: 1097,1109, 2003 [source] d -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] Weight choosability of graphsJOURNAL OF GRAPH THEORY, Issue 3 2009Tomasz Bartnicki Abstract Suppose the edges of a graph G are assigned 3-element lists of real weights. Is it possible to choose a weight for each edge from its list so that the sums of weights around adjacent vertices were different? We prove that the answer is positive for several classes of graphs, including complete graphs, complete bipartite graphs, and trees (except K2). The argument is algebraic and uses permanents of matrices and Combinatorial Nullstellensatz. We also consider a directed version of the problem. We prove by an elementary argument that for digraphs the answer to the above question is positive even with lists of size two. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 242,256, 2009 [source] Multicolored trees in complete graphsJOURNAL OF GRAPH THEORY, Issue 3 2007S. Akbari Abstract A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph K2n(n > 2) with 2n , 1 colors, there are two edge-disjoint multicolored spanning trees. In this paper we generalize this result showing that if (a1,,, ak) is a color distribution for the complete graph Kn, n,,,5, such that , then there exist two edge-disjoint multicolored spanning trees. Moreover, we prove that for any edge coloring of the complete graph Kn with the above distribution if T is a non-star multicolored spanning tree of Kn, then there exists a multicolored spanning tree T' of Kn such that T and T' are edge-disjoint. Also it is shown that if Kn, n , 6, is edge colored with k colors and , then there exist two edge-disjoint multicolored spanning trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 221,232, 2007 [source] On labeling the vertices of products of complete graphs with distance constraintsNAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 2 2005D.J. Erwin Variations of Hale's channel assignment problem, the L(j, k)-labeling problem and the radio labeling problem require the assignment of integers to the vertices of a graph G subject to various distance constraints. The ,j,k -number of G and the radio number of G are respectively the minimum span among all L(j, k)-labelings, and the minimum span plus 1 of all radio labelings of G (defined in the Introduction). In this paper, we establish the ,j,k -number of ,K for pairwise relatively prime integers t1 < t2 < , < tq, t1 , 2. We also show the existence of an infinite class of graphs G with radio number |V(G)| for any diameter d(G). © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2005 [source] Rendezvous search when marks are left at the starting pointsNAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 8 2001Vic Baston Abstract Leaving marks at the starting points in a rendezvous search problem may provide the players with important information. Many of the standard rendezvous search problems are investigated under this new framework which we call markstart rendezvous search. Somewhat surprisingly, the relative difficulties of analysing problems in the two scenarios differ from problem to problem. Symmetric rendezvous on the line seems to be more tractable in the new setting whereas asymmetric rendezvous on the line when the initial distance is chosen by means of a convex distribution appears easier to analyse in the original setting. Results are also obtained for markstart rendezvous on complete graphs and on the line when the players' initial distance is given by an unknown probability distribution. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 722,731, 2001 [source] | |||||||||||||