Geometry.Net - the online learning center
Home  - Pure_And_Applied_Math - Graph Theory
e99.com Bookstore
  
Images 
Newsgroups
Page 8     141-156 of 156    Back | 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8 

         Graph Theory:     more books (100)
  1. Eigenspaces of Graphs (Encyclopedia of Mathematics and its Applications) by Dragos Cvetkovic, Peter Rowlinson, et all 2008-03-01
  2. Graphs Theory and Applications: With Exercises and Problems by Jean-Claude Fournier, 2009-03-23

141. Linear Spaces Of A Graph
Some proofs by S C Locke.
http://www.math.fau.edu/locke/LinearSp.htm
Linear Spaces of a Graph
How to contact me This material comes from some notes for a University of Waterloo course taught by Herb Shank (c. 1975). I have an export of a maple worksheet, showing these operators: http://www.math.fau.edu/Locke/courses/GraphTheory/LinSpGen.htm Back to the Graph Theory Index Let G be a finite, connected, directed graph. If the vertex set of G is ,v ,...,v m and the edge set of G is ,e ,...,e n , then it is useful to consider an oriented edge to be an ordered pair of vertices (say tip first, then tail). So: e i =(v s ,v r would indicate that edge e i is directed from v r to v s
If F is a field, and S is a finite set, let F denote the set of all linear combinations of elements of S with coefficients in F . If addition and scalar multiplication are "coordinatewise", then F is a vector space over F having S as one of its bases. Where unambiguous, the subscript F may be omitted. Despite this notational convention, F is important enough to have a special name, C F (G) . When it is convenient and no misinterpretation is possible, we will write

142. Graphs Glossary
Short definitions with cross-references by Bill Cherowitzo.
http://www-math.cudenver.edu/~wcherowi/courses/m4408/glossary.htm

143. List Of Small Graphs
Information System on Graph Class Inclusions, University of Rostock.
http://wwwteo.informatik.uni-rostock.de/isgci/smallgraphs.html
Contents
  • Graphs ordered alphabetically Graphs ordered by number of vertices 3 vertices 4 vertices ... Special families of graphs
  • Graphs ordered alphabetically
    Note that complements are usually not listed. So for e.g. co-fork, look for fork. Only individual graphs are listed, not families or configurations. ∪ K cross star X ... X
    Graphs ordered by number of vertices
    3 vertices - Graphs are ordered by increasing number of edges in the left column.
    = co-triangle
    triangle = K = C
    back to top
    P
    P
    back to top
    4 vertices - Graphs are ordered by increasing number of edges in the left column.
    K
    K = W
    back to top
    co-diamond
    diamond = K - e = 2-fan
    back to top
    co-paw
    paw = 3-pan
    back to top
    C
    C = K
    back to top
    claw = K
    co-claw
    back to top
    P
    Self complementary back to top
    5 vertices - Graphs are ordered by increasing number of edges in the left column.
    K - e + e = K
    K - e
    back to top
    W
    W
    back to top
    P ∪ P
    P ∪ P
    back to top
    co-gem
    gem = 3-fan
    back to top
    K
    K
    back to top
    K
    K = K ∪ K
    back to top
    co-butterfly = C ∪ K
    butterfly
    back to top
    fork = chair
    co-fork = kite = co-chair = chair
    back to top
    co-dart
    dart
    back to top
    P

    144. Advanced Topics In Graph Algorithms
    Lecture notes by Ron Shamir.
    http://www.math.tau.ac.il/~rshamir/atga/atga.html
    Advanced Topics in Graph Algorithms
    This archive contains material on the course taught by Ron Shamir in the department of Computer Science of Tel-Aviv university , on 10/91-2/92 (Fall 92), 4-6/94 (Spring 94) and 4-6/97 (Spring 97). This was a one-semester graduate course open also to seniors, with one three-hour meeting each week. The course emphasized algorithmic and structural aspects of "nice" graph families, in particular perfect graphs, interval graphs, chordal graphs and comparability graphs.
    In Fall 92 the course was based to a large extent on the classic book of Martin C. Golumbic "Algorithmic Graph Theory and Perfect Graphs' (Academic Press, 1980), and in some parts also on the manuscript "The Art of Combinatorics", by Douglas B. West.
    The Spring 94 and Spring 97 course had a similar basis, but emphasized more recent material, and made a lot of reference to applications in molecular biology. (See the webpage Algorithms for Molecular Biology for much more on these aspects.) Material available:
    • Detailed course outline
      • Spring 97 (HTML)
      • Spring 94 (ASCII)
      • Fall 92 (ASCII)
      • Spring 1997 course material (unorganized; some links were not updated and some material is readable only to TAU browsers. Sorry.)

    145. Degree-Diameter Table For Graphs
    With references and further links.
    http://maite71.upc.es/grup_de_grafs/grafs/taula_delta_d.html

    146. Gordon Royle's Cubic Graphs
    List of cubic graphs maintained by Gordon Royle.
    http://www.csse.uwa.edu.au/~gordon/remote/cubics/
    Cubic Graphs
    This page provides access to the ever popular listings of cubic graphs together with a variety of data relating to these graphs. Please note that these pages are being developed incrementally on an "as-needed" basis, so if you want anything, then just ask me on gordon@cs.uwa.edu.au and unless its a bad time, then I will probably oblige. Most of this work originates from my PhD thesis Constructive Enumeration of Graphs , though the techniques used there are now largely obsolete. At present the best cubic graph generation program is written by, and available from Gunnar Brinkmann. The data from the snarks section was generated by Gunnar, so thanks to him for letting me incorporate it into this database.
    Table of Contents
    All cubic graphs
    Exact numbers of cubic graphs are known by results of Robinson and Wormald for values up to 40 vertices. The cubic graphs on up to 20 vertices, together with some smaller families of high girth cubic graphs on higher numbers of vertices are available. The larger numbers in the table, other than the Robinson/Wormald results are due to Gunnar Brinkmann. Each number in the table below is a link to a file of graphs in format. The largest file is the cubics on 22 vertices at 300Mb.

    147. Gordon Royle's Small Graphs
    Gordon Royle s tables of small graphs with Maple software.
    http://www.csse.uwa.edu.au/~gordon/remote/graphs/
    Small Graphs
    This site is intended to collate much of the data about small graphs that I have to keep on recomputing. It is primarily designed for my own use, but anyone else is free to check out the numbers or the graphs. If you are interested in small graph data that is not here, then feel free to mail me at gordon@maths.uwa.edu.au because I may have just not got around to installing it.
    Table of Contents
    Numbers of graphs
    The exact numbers of graphs on n vertices and e edges can be computed by using Polya enumeration theory. This enables us to produce a series of tables of the following format. The tables were produced by a Maple program written with Brendan McKay (well, he wrote it after joint discussions). Graphs with 4 vertices #edges Connected graphs All graphs Total Tables of this nature are available for the graphs on 1-16 vertices. 1 vx 2 vx 3 vx 4 vx ... 16 vx
    Bipartite graph
    The following table gives the number of connected bipartite graphs separated according to the size of the bipartition. Each row corresponds to a fixed number of vertices, while each column refers to the smaller part of the bipartition. Thus the entry 34 for 7 vertices and m=3 indicates that there are 34 conected bipartite graphs on 7 vertices with partition of size (3,4).

    148. Four Color Theorem A Brief Historical Insight
    An essay by Dominic Verderaime.
    http://student.adams.edu/~verderaimedj/finalEssay/

    149. Some Open Problems
    Compiled by Jerry Spinrad.
    http://www.vuse.vanderbilt.edu/~spin/open.html
    Send comments or new problems to include to spin@vuse.vanderbilt.edu

    150. Some Open Problems
    Open problems and conjectures concerning the determination of properties of families of graphs.
    http://www.eecs.umich.edu/~qstout/constantques.html
    Some Open Problems and Conjectures
    These problems and conjectures concern the determination of properties of families of graphs. For example, one property of a graph is its domination number. For a graph G , a set S of vertices is a dominating set if every vertex of G is in S or adjacent to a member of S . The domination number of G is the minimum size of a dominating set of G . Determining the domination number of a graph is an NP-complete problem, but can often be done for many graphs encountered in practice. One topic of some interest has been to determine the dominating numbers of grid graphs (meshes), which are just graphs of the form P(n) x P(m) , where P(n) is the path of n vertices. Marilynn Livingston and I showed that for any graph G , the domination number of the family G x P(n) has a closed formula (as a function of n ), which can be found computationally. This appears in M.L. Livingston and Q.F. Stout, ``Constant time computation of minimum dominating sets'', Congresses Numerantium (1994), pp. 116-128.
    Abstract
    Paper.ps

    151. Problems In Signed, Gain, And Biased Graphs
    Compiled by Thomas Zaslavsky.
    http://www.math.binghamton.edu/zaslav/Bsg/sgbgprobs.html
    Problems in Signed, Gain, and Biased Graphs
    Compiled by Thomas Zaslavsky
    This is a fairly miscellaneous and incomplete selection of problems that I happen to have taken an interest in not necessarily an active interest. Some are open and some are solved or partially solved as for example a problem may have been shown to be NP-complete but special cases could still be solved exactly or algorithmically. This list is intended to supplement the many problems in the Bibliography . There is just a small amount of duplication. For the present, the problems here all concern signed graphs. However, many of them have obvious generalizations. References are as cited in the Bibliography . All the terms employed should be defined in the Glossary . If you find any missing, or if you have suggestions for this page, please notify me! NOTE: A PostScript version is available. It is slightly more up-to-date and it is the only one that will be maintained and expanded.
    I. Direct Measures of Imbalance
    (June 8-10 1998) Imbalance of a signed graph can be measured in numerous ways. Here are problems concerning some measures that have appeared in the literature. The greatest interest has been in the edge version of frustration. (The problems in part II can be regarded as measuring imbalance in a different way.)

    152. Perfect Graphs
    Conjectures and open problems, maintained at the AIM.
    http://www.aimath.org/WWN/perfectgraph/
    Perfect Graphs
    This web page highlights some of the conjectures and open problems concerning Perfect Graphs. If you would like to print a hard copy of the whole outline, you can download a dvi postscript or pdf version.
  • Recognition of Perfect Graphs Polynomial Recognition Algorithm Found Interaction Between Skew-Partitions and 2-joins The Perfect-Graph Robust Algorithm Problem ... A Possible New Problem Skew-Partitions Extending a Skew -Partition Graphs Without Skew-Partitions Graphs Without Star Cutsets Finding Skew-Partitions in Berge Graphs ... beta-perfect graphs Partitionable Graphs Perfect, Partitionable, and Kernel-Solvable Graphs Partitionable graphs and odd holes A Property of Partitionable Graphs Small Transversals in Partitionable Graphs ... The Imperfection Ratio Integer Programming Partitionable Graphs as Cutting Planes for Packing Problems? Feasibility/Membership Problem For the Theta Body Balanced Graphs Balanced circulants ... P4-structure and Its Relatives
  • The individual contributions may have problems because converting complicated TeX into a web page is not an exact science. The dvi, ps, or pdf versions are your best bet.

    153. Open Problems On Perfect Graphs
    Unsolved problems on perfect graphs.
    http://www.cs.concordia.ca/~chvatal/perfect/problems.html
    PERFECT PROBLEMS
    Created on 22 August, 2000
    Last updated on 5 July, 2006
    In May 2002,
    the Strong Perfect Graph Conjecture
    became
    the Strong Perfect Graph Theorem
    Details are here.
    As a part of the 1992 1993 Special Year on Combinatorial Optimization at DIMACS ftp://dimacs.rutgers.edu/pub/perfect/problems.tex
    If you have
    • information on progress towards solving these problems or
    • complaints in case I did not give credit where credit was due or
    • suggestions for problems to add,
    please, send them to me
    Related pages: This collection is written for people with at least a basic knowledge of perfect graphs. Uninformed neophytes may look up the missing definitions on the web in Alexander Schrijver's lecture notes or in Jerry Spinrad's draft of a book on efficient graph representations etc. or in MathWorld . Books on perfect graphs include

    154. Erdös Number Project - The Erdös Number Project - Oakland University
    List of people with Erdos number at most 2.
    http://www.oakland.edu/enp/

    155. Tom Whaley
    Formal development of programs, Steinhaus graphs, parallel computing.
    http://home.wlu.edu/~whaleyt/
    Tom Whaley
    Department of Computer Science
    Washington and Lee University
    General information
    Professor
    Department of Computer Science

    Washington and Lee University

    Office: 406 Parmly (Science Center)
    Phone: 540-458-8813
    Schedule - Fall 2007 Mon Tue Wed Thur Fri A B 101 L C 101 L D 101 L E F G 101 L H 101 L I 101 L Legend In class Office Gotta life Maybe
    Current Courses
    CS 101 - Survey of Computer Science
    Current Projects
    Alsos Digital Library for Nuclear Issues

    156. Keith Edwards' Home Page
    Harmonious colourings and achromatic number.
    http://www.maths.dundee.ac.uk/~kedwards/
    Keith Edwards
    Address:
    School of Computing University of Dundee Dundee
    E-mail: Phone:
    Research Interests:
    Graph Theory Algorithms
    • Algorithms for Graphs Problems NP-Completeness
    Links of interest
    This page is the personal responsibility of Keith Edwards. The views expressed here do not necessarily represent the official views of the University.

    Page 8     141-156 of 156    Back | 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8 

    free hit counter