Ermelinda DeLaVina
Professor of Mathematics
University of Houston - Downtown


My Publications

Lists of Conjectures

On Graph Listings & Graph Invariants

  • For collections of graphs see B. McKay's combinatorial data page.
  • For a listing and drawings of small graphs and Java applet for investigating classes of graphs see ISCGI project.
  • For some tables of graphs, computed graph invariants and conjectures see S. Speed's page.
  • For some tables of distributions of computed graph invariants (chromatic number & chromatic index) see K  Briggs page.
  • While working on improving the performance of some of my code for various dominating sets, I found the following distributions interesting.
    The following are frequencies of values for all connected 9-vertex graphs, where g is the domination number, gt is the total domination number, i is the independent domination number, g2 is the 2-domination number (double-domination), a is the independence number, acrit is the critical independence number and acore the order of the intersection of all maximum independent sets.


    # with g=value # with gt=value # with i=value # with g2=value # with a=value # with acrit=value # with acore=value
    0 0 0 0 0 0 184593 84231
    1 12346 0 12346 0 1 33235 32914
    2 219823 183149 198678 2054 1892 11913 33683
    3 28720 70667 49086 102428 100702 8529 39855
    4 191 7151 969 132775 135563 254 54593
    5   111 1 22007 21782 21419 14835
    6   2   1729 1105 1102 936
    7       84 34 34 32
    8       3 1 1 1

Graffiti History and My Collaboration on Graffiti

  • Graffiti is a computer program that makes conjectures in mathematics and chemistry. Around 1985, Siemion Fajtlowicz developed the first version of Graffiti, which generated conjectures of interest to many well known researchers. A list of conjectures of Graffiti, Written on the Wall, maintained by Fajtlowicz.  I update a growing bibliography of many papers inspired by Graffiti (which also includes some that simply mention or compare Graffiti.) 
  • My collaboration with Fajtlowicz on Graffiti began around 1990 (as his student), at this time we began developing the newest versions of Graffiti, called Forever, Whatever and Dalmatians. Some descriptions of these versions are available in my paper On Some History of the Development of Graffiti (2003)  and also in papers by Fajtlowicz and Larson.
  • In addition to co-authoring the new versions and resolving many conjectures, I have resumed extending the list of conjectures Written on the Wall II  generated by Graffiti (conjectures 1-8) and now also Graffiti.pc (conjectures 9 and on.) 

Educational Applications of Graffiti (and Graffiti.pc)

  • In the Spring of 2001, as an educational experiment, my undergraduate student Barbara Chervenka explored graph theory through conjectures of Graffiti. She maintained a chronology of conjectures and their resolutions, and presented a poster at Combinatexas 2001). On the similar topic she gave a Pi Mu Epsilon student presentation titled "Exploring Graph Theory Through Conjectures of Graffiti" at MathFest 2001, and at DIMACS in 2001 discussing her use of Graffiti.pc. In the Summer of 2001, another of my undergraduate students Kelly Wroblewski conducted a similar project utilizing Graffiti.pc and presented the results of the project in the poster session of the CST Student Research Conference in November 2001. There is a page with these and all subsequent Graffiti.pc undergraduate projects
  • In the spring of 2002, Gunnar Brinkmann at the University of Bielefeld (Germany) also used Graffiti.pc for a graduate mathematics education course.. Further, in the spring of 2004 he conducted a workshop for advanced high school teachers.
  • For similar applications, see Fajtlowicz's webpage and Ryan Pepper's paper "On New Didactics of Mathematics: Learning Graph Theory via Graffiti"..


  • In the summer of 2001, I developed a pc-platform program called Graffiti.pc. For a description of my program and of the above mentioned educational applications see my paper, Graffiti.pc: A Variant of Graffiti (2002) (pdf).


[Back to DeLaVina's Homepage]