Retracts of hypercubes

An induced subgraph G of a graph H is a retract of H if there is an edge-preserving map f from H onto G such that f|_G is the identity map on G. A median graph is a connected graph such that for any three vertices u,v and w, there exists a unique vertex x which lies simultaneously on some shortest (u,v)-, (v,w)-, and (w,u)-paths. It is shown that a graph G is a retract of some hypercube if and only if G is a median graph.     

n-cubes and median graphs

The n-cube is characterized as a connected regular graph in which for any three vertices u, v, and w there is a unique vertex that lies simultaneously on a shortest (u, v)-path, a shortest (v, w)-path, and a shortest (w, u)-path.     

On simplices in diameter graphs in ℝ4

Agraph G is a diameter graph in ?^d if its vertex set is a finite subset in ?^d of diameter 1 and edges join pairs of vertices a unit distance apart. It is shown that if a diameter graph G in ?⁴ contains the complete subgraph K on five vertices, then any triangle in G shares a vertex with K. The geometric interpretation of this statement is as follows. Given any regular unit simplex on five vertices and any regular unit triangle in ?⁴, then either the simplex and the triangle have a common vertex or the diameter of the union of their vertex sets is strictly greater than 1.

     

LOCALIZATION THEOREM ON HAMILTONIAN GRAPHS

1IntroductionInthispaper,Weuse[1]forterminologyandnotationnotdefinedhereandconsiderfinitesillWlegraphsonlyThedistancebetweenverticesuandvisdenotedbyd(u,v)-ForeachvertexuEV(G),wedeuotebyN(u)thesetofallverticesofGadjacenttou.ThesubgraphofGinducedbyN(u)U{u}isdenotedbyG(u).IfuveE(G),wedenotebyS(u,v)thenumberofedgesofmaximumstarincludingu5vasaninducedsubgraphinG.Letxai1dybetwoverticesinGwitl1d(x,y)=2,wedefineI(x,y)=IN(x)nN(y)I.LetCbeacycleofGwithafixedcyclicorientation.ForuEV(C),letu be…     

Claw Conditions for Heavy Cycles in Weighted Graphs

A graph is called a weighted graph when each edge e is assigned a nonnegative number w(e), called the weight of e. For a vertex v of a weighted graph, d^w(v) is the sum of the weights of the edges incident with v. For a subgraph H of a weighted graph G, the weight of H is the sum of the weights of the edges belonging to H. In this paper, we give a new sufficient condition for a weighted graph to have a heavy cycle. A 2-connected weighted graph G contains either a Hamilton cycle or a cycle of weight at least c, if G satisfies the following conditions: In every induced claw or induced modified claw F of G, (1) max{d^w(x),d^w(y)} c/2 for each non-adjacent pair of vertices x and y in F, and (2) all edges of F have the same weight.     

赋权图的w密度和w平衡性

The notion of w-density for the graphs with positive weights on vertices and nonnegative weights on edges is introduced. A weighted graph is called w-balanced if its w-density is no less than the w-density of any subgraph of it. In this paper,a good characterization of w-balanced weighted graphs is given. Applying this characterization ,many large w-balanced weighted graphs are formed by combining smaller ones. In the case where a graph is not w-balanced,a polynomial-time algorithm to find a subgraph of maximum w-density is proposed. It is shown that the w-density theory is closely related to the study of SEW(G,w) games.     

Hereditary modular graphs

In a hereditary modular graphG, for any three verticesu, v, w of an isometric subgraph ofG, there exists a vertex of this subgraph that is simultaneously on some shortestu, v-path,u, w-path andv, w-path. It is shown that the hereditary modular graphs are precisely those bipartite graphs which do not contain any isometric cycle of length greater than four. There is a polynomial-time algorithm available which decides whether a given (bipartite) graph is hereditary modular or not. Finally, the chordal bipartite graphs are characterized by forbidden isometric subgraphs.     

An exact algorithm for subgraph homeomorphism

The subgraph homeomorphism problem is to decide if there is an injective mapping of the vertices of a pattern graph into vertices of a host graph so that the edges of the pattern graph can be mapped into (internally) vertex-disjoint paths in the host graph. The restriction of subgraph homeomorphism where an injective mapping of the vertices of the pattern graph into vertices of the host graph is already given in the input instance is termed fixed-vertex subgraph homeomorphism.We show that fixed-vertex subgraph homeomorphism for a pattern graph on p vertices and a host graph on n vertices can be solved in time 2^n−pn^O(1) or in time 3^n−pn^O(1) and polynomial space. In effect, we obtain new non-trivial upper bounds on the time complexity of the problem of finding k vertex-disjoint paths and general subgraph homeomorphism.     

A New Class of Brittle Graphs

A graph G is perfectly orderable in the sense of Chvátal if there exists a linear order on the set of vertices of G such that no induced path with vertices a, b, c, d and edges ab, bc, cd has a < b and d < c. A perfectly orderable graph G is brittle if every induced subgraph of G contains a vertex which is either endpoint or midpoint of no induced path with three edges in G. We present a new class of brittle graphs by forbidden configurations.     

Amply regular graphs and block designs

We study the amply regular diameter d graphs Γ such that for some vertex a the set of vertices at distance d from a is the set of points of a 2-design whose set of blocks consists of the intersections of the neighborhoods of points with the set of vertices at distance d-1 from a. We prove that the subgraph induced by the set of points is a clique, a coclique, or a strongly regular diameter 2 graph. For diameter 3 graphs we establish that this construction is a 2-design for each vertex a if and only if the graph is distance-regular and for each vertex a the subgraph Γ₃(a) is a clique, a coclique, or a strongly regular graph. We obtain the list of admissible parameters for designs and diameter 3 graphs under the assumption that the subgraph induced by the set of points is a Seidel graph. We show that some of the parameters found cannot correspond to distance-regular graphs.     

On connection between the switching separability of a graph and its subgraphs

A graph of order n ≥ 4 is called switching separable if its modulo-2 sum with some complete bipartite graph on the same set of vertices is divided into two mutually independent subgraphs, each having at least two vertices. We prove the following: If removing any one or two vertices of a graph always results in a switching separable subgraph then the graph itself is switching separable. On the other hand, for each odd order greater than 4, there is a graph that is not switching separable, but removing a vertex always results in a switching separable subgraph. We show some connection with similar facts on the separability of Boolean functions and the reducibility of n-ary quasigroups.     

Uniqueness and nonexistence of some graphs related toM 22

There is a unique distance regular graph with intersection array i (7, 6, 4, 4; 1, 1, 1, 6); it has 330 vertices, and its automorphism groupM ₂₂.2 acts distance transitively. It does not have an antipodal 2-cover, but it has a unique antipodal 3-cover, and this latter graph has automorphism group 3.M ₂₂.2 acting distance transitively. As a side result we show uniqueness of the strongly regular graph with parameters (v, k, , ) = (231, 30, 9, 3) under the assumption that it is a gamma space with lines of size 3.     

关于赋权图中重圈的一个范型定理

设G=(V, E; w)为赋权图,定义G中点v的权度d_G^w(v)为G中与v相关联的所有边的权和.该文证明了下述定理: 假设G为满足下列条件的2 -连通赋权图: (i) 对G中任何导出路xyz都有w(xy)=w(yz); (ii)对G中每一个与K_1,3或K_1,3+e同构的导出子图T, T中所有边的权都相等并且min{max{d_G^w(x), d^w_G(y)}:d(x,y)=2,x,y∈ V(T)}≥ c/2. 那么, G中存在哈密尔顿圈或者存在权和至少为 c 的圈. 该结论分别推广了Fan^[5], Bedrossian等人^[2]和Zhang等人^[7]的相关定理     

Induced subgraphs of prescribed size

A subgraph of a graph G is called trivial if it is either a clique or an independent set. Let q(G) denote the maximum number of vertices in a trivial subgraph of G. Motivated by an open problem of Erd?s and McKay we show that every graph G on n vertices for which q(G)≤ C log n contains an induced subgraph with exactly y edges, for every y between 0 and n^{δ (C)}. Our methods enable us also to show that under much weaker assumption, i.e., q(G) ≤ n/14, G still must contain an induced subgraph with exactly y edges, for every y between 0 and . © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 239–251, 2003     

New Local Conditions for a Graph to be Hamiltonian

For a vertex w of a graph G the ball of radius 2 centered at w is the subgraph of G induced by the set M₂(w) of all vertices whose distance from w does not exceed 2. We prove the following theorem: Let G be a connected graph where every ball of radius 2 is 2-connected and d(u)+d(v)≥|M₂(w)|−1 for every induced path uwv. Then either G is hamiltonian or for some p≥2 where ∨ denotes join. As a corollary we obtain the following local analogue of a theorem of Nash-Williams: A connected r-regular graph G is hamiltonian if every ball of radius 2 is 2-connected and for each vertex w of G. Supported by the Swedish Research Council (VR)     

Bounds related to domination in graphs with minimum degree two

A dominating set for a graph G = (V,E) is a subset of vertices V′ ⊆ V such that for all v E V − V′ there exists some u E V′ for which {v, u} E E. The domination number of G is the size of its smallest dominating set(s). We show that for almost all connected graphs with minimum degree at least 2 and q edges, the domination number is bounded by (q + 1)/3. From this we derive exact lower bounds for the number of edges of a connected graph with minimum degree at least 2 and a given domination number. We also generalize the bound to k-restricted domination numbers; these measure how many vertices are necessary to dominate a graph if an arbitrary set of k vertices must be incluced in the dominating set. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 139–152, 1997     

Long cycles and spanning subgraphs of locally maximal 1-planar graphs

A graph is 1-planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a complete subgraph, then the graph is locally maximal 1-planar. For a 3-connected locally maximal 1-planar graph G, we show the existence of a spanning 3-connected planar subgraph and prove that G is Hamiltonian if G has at most three 3-vertex-cuts, and that G is traceable if G has at most four 3-vertex-cuts. Moreover, infinitely many nontraceable 5-connected 1-planar graphs are presented.     

Complete subgraphs with large degree sums

Let t(n, k) denote the Turán number—the maximum number of edges in a graph on n vertices that does not contain a complete graph K_k+1. It is shown that if G is a graph on n vertices with n ≥ k²(k – 1)/4 and m < t(n, k) edges, then G contains a complete subgraph K_k such that the sum of the degrees of the vertices is at least 2km/n. This result is sharp in an asymptotic sense in that the sum of the degrees of the vertices of K_k is not in general larger, and if the number of edges in G is at most t(n, k) – ? (for an appropriate ?), then the conclusion is not in general true. © 1992 John Wiley & Sons, Inc.     

A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs

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,E_S), E_S ⊆ 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     

On the hamiltonian path graph of a graph

The hamiltonian path graph H(F) of a graph F is that graph having the same vertex set as F and in which two vertices u and v are adjacent if and only if F contains a hamiltonian u ? v path. First, in response to a conjecture of Chartrand, Kapoor and Nordhaus, a characterization of nonhamiltonian graphs isomorphic to their hamiltonian path graphs is presented. Next, the maximum size of a hamiltonian graph F of given order such that K?_d ? H(F) is determined. Finally, it is shown that if the degree sum of the endvertices of a hamiltonian path in a graph F with at least five vertices is at least |V(F)| + t(t ? 0), then H(F) contains a complete subgraph of order t + 4.