Coordinate Graphs

Some bars may involve many Pairs of numbers.A bar for eaeh pair would take up too mueh spaee.CoordinategraPhs are used instead.ExamPleBelow 15 a table of temPeratures for a eold January morning in Minneapolis.Put this information onto a eoordinategraPh. Time of day TemPerature(。F) 1 A.M.一2 2 A.M.一2 3 A.M.一2 4 A.M.一1 5 A.M.O 6 A.M.3 7 A.M.一1 8 A.M.O 9 A.M.3 10 A.M.7 1 1 A.M.11 12 noon 18SolutionThis eoordinate graph 15 based on two number lines.The horizontal number line r…     

On Compact Graphs

Let G be a finite simple graph with adjacency matrix A, and let P（A） be the convex closure of the set of all permutation matrices commuting with A. G is said to be compact if every doubly stochastic matrix which commutes with A is in P（A）. In this paper, we characterize 3-regular compact graphs and prove that if G is a connected regular compact graph, G - v is also compact, and give a family of almost regular compact connected graphs.     

On Factor-Uniform Graphs

Graphsunderconsiderationarefiniteundirected,andbasicgraph-theoreticnotationandtermsusedarethesamewiththatin[1].LetG=(V(G),E(G))beagraphwhichmayhaveloopsormultipleedges,Z~{0,if,12,.'.},g,f:V(G)-Z,p(g,f)~{xEV(G)lg(x)~f(x)}andp(g,f)GPgV(G).Supposeg(x)5f(x)forallxEV(G)andg(x)~f(x)(mod2)forallxEP.Thena(P,f)-congruent(g,f)-factorofGisaspanningsubgraphFofGsuchthatg(x)5dF(x)5f(x)forallxEV(G)anddF(x)~f(x)(mod2)forallxCP.Giscalled(g,f;p)-covered(-deleted,resp.)if,foreachedgeeofG,thereexist…     

Cuts,Trees and ℓ<Subscript>1</Subscript>-Embeddings of Graphs*

Motivated by many recent algorithmic applications, this paper aims to promote a systematic study of the relationship between the topology of a graph and the metric distortion incurred when the graph is embedded into ₁ space. The main results are:1. Explicit constant-distortion embeddings of all series-parallel graphs, and all graphs with bounded Euler number. These are the first natural families known to have constant distortion (strictly greater than 1). Using the above embeddings, algorithms are obtained which approximate the sparsest cut in such graphs to within a constant factor.2. A constant-distortion embedding of outerplanar graphs into the restricted class of ₁-metrics known as dominating tree metrics. A lower bound of (log n) on the distortion for embeddings of series-parallel graphs into (distributions over) dominating tree metrics is also presented. This shows, surprisingly, that such metrics approximate distances very poorly even for families of graphs with low treewidth, and excludes the possibility of using them to explore the finer structure of ₁-embeddability.* A preliminary version of this work appeared in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999, pp. 399–408. This work was done while the author was at the University of California, Berkeley. Supported in part by NSF grants CCR-9505448 and CCR-9820951.     

Vertex-transitive Diameter Two Graphs

We investigate the family of vertex-transitive graphs with diameter 2. Let Γ be such a graph.Suppose that its automorphism group is transitive on the set of ordered non-adjacent vertex pairs. Then either Γ is distance-transitive or Γ has girth at most 4. Moreover, if Γ has valency 2, then Γ≌ C₄ or C₅; and for any integer n ≥ 3, there exist such graphs Γ of valency n such that its automorphism group is not transitive on the set of arcs. Also, we determine this family of grap...     

ε-Unit Distance Graphs

We consider a variation on the problem of determining the chromatic number of the Euclidean plane and define the -unit distance graph to be the graph whose vertices are the points of E², in which two points are adjacent whenever their distance is within of 1. For certain values of we are able to show that the chromatic number is exactly 7. For some smaller values we show the chromatic number is at least 5. We offer a conjecture, with some supporting evidence, that for any > 0 the chromatic number is 7.     

ℓ1-Rigid Graphs

An ₁-graph is a graph whose nodes can be labeled by binary vectors in such a way that the Hamming distance between the binary addresses is, up to scale, the distance in the graph between the corresponding nodes. We show that many interesting graphs are ₁-rigid, i.e., that they admit an essentially unique such binary labeling.     

The Maximum Size and Related Extremal Graphs of Critically h-Edge-Connected Graphs

Let G be a simple graph.The edge-connectivity of G is denoted by λ(G). For a given positive integer h,G is said to be critically h-edge-connected ifλ(G)=h and λ(G-χ)相似文献   

Disjoint Paths in Graphs I,¶3-planar Graphs and Basic Obstructions

Let G be a graph,{a,b,c} í V(G) \{a,b,c\}\subseteq V(G) , and {a￠,b￠,c￠} í V(G) \{a',b',c'\}\subseteq V(G) such that {a,b,c} 1 {a￠,b￠,c￠} \{a,b,c\}\neq \{a',b',c'\} . We say that (G,{a,c}, {a￠,c￠}, (b, b￠)) (G,\{a,c\}, \{a',c'\}, (b, b')) is an obstruction if, for any three vertex disjoint paths from {a, b, c} to {a', b', c'} in G, one path is from b to b'. Robertson and Seymour asked the problem of characterizing all obstructions. In this paper, we present a list of "basic" obstructions and show how to produce other obstructions from these basic ones. We also prove results about disjoint paths in graphs. Results in this paper will be used in subsequent papers to characterize all obstructions.     

The Linear Arboricity of Graphs

Inthispaper,allgraphsarefinite,simpleandundirected.Forarealnumberx,[x]istheleastintegernotlessthanx.LetG＝(V(G),E(G))beagraph.Weuse△(G)andδ(G)todenotethemaximum(vertex)degreeandtheminimum(vertex)degreeofG.Letw(G)＝min{d(u) d(v):uv∈E(G)}.Thegirthg(G)ofGistheminimumlengthofcycles.Thedensitymad(G)ofagraphGisthemaximumvalueof2|E(H)|/|V(H)|takenoverallsubgraphsHofG.Ifv6V(G),N(v)denotesthesetofvenicesadjacenttov,thedegreedG(v)isING(v)landNc(v)={aluEN(v)andd(u)=k}.Avertexofdegreekisc…     

Decycling Number of Some Graphs

1.IntroductionInthispaper,weonlydiscusssimplegraph(withneithermulti-edgenorloop).TheterminologiesnotexplainedcanbeseeninII].Thecyclerankofagraphistheminimumnumberofedgesthatmustberemovedinordertoeliminateallofthecyclesinthegraph.IfGhaspvenices,qedges...     

The Erd?s–Sós Conjecture for Graphs withoutC4

Erd?s and Sós conjectured in 1963 that ifGis a graph of ordernand sizee(G) with, thenGcontains every treeTof sizek. We prove the conjecture in the case whereGdoes not contain the cycleC₄.     

Quasi-I-Hamilton Connectedness of Tree Graphs

For any graph G, Γ(G) is uniformly hamiltonian whenever it contains at least two cycles [1] and is either a hypercube or hamilton connected [2].In this paper, a further investigation to the hamiltonian property of tree graphs will be made.     

p-arrangeable Graphs are Folkman Linear

For graphs F and G,let F→(G,G)denote that any red/blue edge coloring of F contains a monochromatic G.Define Folkman number f(G;t)to be the smallest order of a graph F such that F→(G,G)andω(F)≤t.It is shown that f(G;t)≤cn for p-arrangeable graphs with n vertices,where p≥1,c=c(p)and t=t(p)are positive constants.     

On k-ordered Graphs Involved Degree Sum

Abstract A graph G is k-ordered Hamiltonian,2≤k≤n,if for every ordered sequence S of k distinctvertlces of G,there exists a Hamiltonian cycle that encounters S in the given order. In this article, we provethat if G is a graph on n vertices with degree sum of nonadjacent vertices at least n+3k-9/2,then G is k-orderedHamiltonian for k=3,4,…,[n/19].We also show that the degree sum bound can be reduced to n+2[k/2]-2 ifk(G)≥3k-1/2 or δ(G)≥5k-4.Several known results are generalized.     

Self Complement Graphs on 8 Vertices

In this note we deduce that there are exactly 10 self complement graphs on 8 vertices (G), which is characterized in the sort of degree sequences. It is a correction to the assertation made by Harary([1]).     

Pancyclism and Bipancyclism of Hamiltonian Graphs

A graph G on n vertices is called pancyclic if it contains cycles of everylength k, for 3≤k≤n. A bipartite graph on 2n vertices is called bipancyclicif it contains cycles of every even length 2k, for 2≤k≤n. In this paper,we consider only finite, undirected graphs without loops ormultipie edges. We shall give a new sufficient condition ensuring a Hamiltonian graph tobe pancyclic(or bipancyclic), The main results are the following two theorems.Theorem A. Let G be a Hamiltonian graph of order n. If there exisis a     

The Entire Coloring of Series-Parallel Graphs

The entire chromatic number X_(vef)(G) of a plane graph G is the minimal number of colors needed for coloring vertices, edges and faces of G such that no two adjacent or incident elements are of the same color. Let G be a series-parallel plane graph, that is, a plane graph which contains no subgraphs homeomorphic to K_(4-) It is proved in this paper that X_(vef)(G)≤max{8, △(G) 2} and X_(vef)(G)=△ 1 if G is 2-connected and △(G)≥6.     

Super-edge-graceful Labelings of Some Cubic Graphs

The notion of super-edge-graceful graphs was introduced by Mitchem and Simoson in 1994.However, few examples except trees are known. In this paper, we exhibit two classes of infinitely many cubic graphs which are super-edge-graceful. A conjecture is proposed.