Terry McKee Home Terry A McKee

Department of Mathematics and Statistics Department of Mathematics and Statistics

College of Science and Mathematics College of Science and Mathematics

Wright State Home Wright State Home

 

Professor Emeritus, Mathematics and Statistics
Wright State University
3640 Colonel Glenn Highway
Dayton OH 45435-0001


messages 937.775.2785


fax 937.775.2081
 

long gold bar

Graph Duality/Dualities Papers

"Dualizing distance-hereditary graphs," Discussiones Mathematicae Graph Theory to appear.

"Dual-chordal and strongly dual-chordal graphs," Journal of Combinatorial Mathematics and Combinatorial Computing 93 (2015) 53-63.

gold spacer bar

"When fundamental cycles span cliques," Congressus Numerantium 191 (2009) 213-218.

This paper explores a duality between the maximal cliques and the unit disks of a graph.

gold spacer bar

"S-minimal unions of disjoint cycles and more odd eulerian characterizations," Congressus Numerantium 177 (2005) 129-132.

"Dualizing chordal graphs," Discrete Mathematics 263 (2003) 207-219.

"Recognizing dual-chordal graphs," Congressus Numerantium 150 (2001) 97-103.

gold spacer bar

"Graph-theoretic model of geographic duality," Annals of the New York Academy of Sciences 555 (1989) 310-315.

A graph-theoretical look at the dual tree structures of watercourses (streams) and watersheds (divides), including the isthmus/strait duality and a self-dual, Euleresque role of bridges.

gold spacer bar

"A clique/kernel analog of eulerian," Congressus Numerantium 64 (1988) 171-178.

gold spacer bar

"Dualizing cubic graph theory," Fundamenta Mathematicae 130 (1988) 67-72.

"Dual properties within graph theory," Fundamenta Mathematicae 128 (1987) 91-97.

These two papers emphasize the commonly overlooked fact that concepts cannot be dualized; only particular formulations of the concepts can be.

gold spacer bar

"A logical analogy between directed and signed graphs," Utilitas Mathematica 32 (1987) 175-180.

gold spacer bar

"The logic of graph-theoretic duality," American Mathematical Monthly 92 (1985) 457-464.

A more accessible discussion of my "cycle-logical" approach to graph duality, plus a rather unexpected duality between spanning trees and edge cutsets.

gold spacer bar

"Balance and duality in signed graphs," Congressus Numerantium 44 (1984) 11-18.

gold spacer bar

"Recharacterizing eulerian: intimations of new duality," Discrete Mathematics 51 (1984) 237-242.

This is where the characterization of a connected graph being eulerian iff every edge is in an odd number of cycles (and being bipartite iff every edge is in an odd number of cutsets) first appeared, embedded in matroids and logic. You would probably prefer looking at the following instead (or the Chartrand & Lesniak or Chartrand & Oellermann textbooks):

H. Fleischner, "Elementary proofs of (relatively) recent characterizations of Eulerian graphs," Discrete Applied Mathematics 24 (1989) 115-119.

D. R. Woodall, "A proof of McKee's Eulerian-bipartite characterization," Discrete Mathematics 84 (1990) 217-220.

gold spacer bar

"Logical aspects of combinatorial duality," Canadian Mathematical Bulletin 27 (1984) 251-242.

"Prime implicant quantifiers for matroids, graphs, and switching networks," Utilitas Mathematica 24 (1983) 155-163.

gold spacer bar

"Duality principles for binary matroids and graphs," Discrete Mathematics 43 (1983) 215-222.

"A quantifier for matroid duality," Discrete Mathematics 34 (1981) 315-318.

These papers show how the traditional cycle/cutset duality of graph theory corresponds to the duality of the universal and existential quantifiers in logic.

gold spacer bar

"Logical and matroidal duality in combinatorial linear programming," Congressus Numerantium 29 (1980) 667-672.

"A self-dual language for graph theory," Journal of Combinatorial Theory (B) 21 (1979) 60-66.

long gold bar
Terry A McKee home page
Course information  | Brief vita
Topics in Intersection Graph Theory
corrections/updates; ordering information and review
Intersection graphs | Graph duality  | Graph meta-theory | Miscellaneous graph theory | Mathematical logic | Truly miscellaneous

long gold bar

This web site was last updated February 22, 2003.
Email me your comments, questions and suggestions concerning this site. (sjm)

Official WSU disclaimer.