From lieber@ccs.neu.edu Thu Jan 16 10:21:43 2003 X-UIDL: $%3"!nl,"!lN>"!KI("! Return-Path: Delivered-To: lieber@ccs.neu.edu Received: from ibm782cdt7 (bendel.ccs.neu.edu [129.10.118.162]) by amber.ccs.neu.edu (Postfix) with SMTP id C87066B4F2 for ; Thu, 16 Jan 2003 10:21:42 -0500 (EST) Reply-To: From: "Karl Lieberherr" To: "Lieber@Ccs.Neu.Edu" Subject: Graph Product -- from MathWorld.htm Date: Thu, 16 Jan 2003 10:25:01 -0500 Message-ID: MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_NextPart_000_0063_01C2BD49.878AD480" X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2911.0) Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 X-Spam-Status: No, hits=2.4 required=5.0 tests=AWL,FROM_AND_TO_SAME_6,HTML_50_70,HTML_FONT_COLOR_GRAY, HTML_FONT_INVISIBLE,MAILTO_LINK,MIME_EXCESSIVE_QP, MIME_LONG_LINE_QP,SPAM_PHRASE_00_01,TO_ADDRESS_EQ_REAL, USER_AGENT_OUTLOOK version=2.43 X-Spam-Level: ** Status: RO Content-Length: 23344 This is a multi-part message in MIME format. ------=_NextPart_000_0063_01C2BD49.878AD480 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit ------=_NextPart_000_0063_01C2BD49.878AD480 Content-Type: text/html; name="Graph Product -- from MathWorld.htm" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="Graph Product -- from MathWorld.htm" =0A= =0A= =0A= =0A= Graph Product -- from MathWorld=0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A=
3D"Wolfram3D"Wolfram3D"MathWorld"3D"MathWorld"
3D"Research"3D"www.wolfram.com"3D"Products"=0A=3D"Services"=0A=3D"Solutions"=0A=3D"Resource3D"News"=0A=3D"Online3D"Our
=0A=
=0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A=
=0A= 3D""
=0A=
=0A= 3D""
=0A=
=0A= 3D"Wolfram=0A= =0A= 3D"Astronomy"=0A= 3D"Biography"=0A= 3D"Chemistry"=0A= 3D"Mathematics"=0A= 3D"Physics"=0A=
=0A= =0A= =0A= =0A= =0A= 3D""=0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A=
=0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A=
=0A= 3D"MathWorld
=0A=
=0A= 3D""
=0A=
=0A=    3D""=0A= =0A= =0A= =0A= =0A= =0A=
=0A=    =0A=  =0A= =0A= =0A= =0A= =0A=
=0A=
=0A=
=0A= 3D""
=0A= 3D"Index
=0A= 3D""
=0A= 3D"Alphabetical
=0A= 3D""
=0A= 3D"About
=0A= 3D""
=0A= 3D"Eric's=0A=
=0A= 3D""
=0A= 3D"Order
=0A= 3D""
=0A= =0A= =0A= 3D"Algebra"=0A= 3D"Applied =0A= 3D"Calculus=0A= 3D"Discrete=0A= 3D"Foundations=0A= 3D"Geometry"=0A= 3D"History=0A= 3D"Number=0A= 3D"Probability=0A= 3D"Recreational=0A= 3D"Topology"=0A= =0A= =0A= =0A= 3D"About=0A= 3D"Author's=0A= 3D"FAQ"=0A= 3D"What's=0A= 3D"Random=0A= 3D"Contribute"=0A= 3D"Sign=0A= 3D"Email=0A= 3D"How=0A= 3D"Terms=0A= =0A= =0A= =0A= =0A= =0A= =0A= 		3D""=0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A=
  Discrete Mathematics  3D"">   Graph Theory  3D"">   Graph Operations  3D"v" 
=0A= =0A= =0A= =0A= =0A= =0A= =0A=
  Math Contributors  <= /font>3D"">   Bray  3D"v" 
=0A= =0A= =0A= =0A= =0A= =0A= =0A=

=0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A=
3D""
3D""
Graph Product3D""
=0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A=
3D""
3D""
3D""    =0A= =0A=

=0A= =0A= =0A= =0A= =0A= This entry contributed by Nicolas Bray

=0A= In general, a graph product of two graphs G and H is a new = graph whose vertex set is =0A= =0A= and=0A= where, for any two vertices (g, h) and in the product, the adjacency of those two = vertices is determined=0A= entirely by the adjacency (or equality, or non-adjacency) of g = and , and that of h and . There are =0A= =0A= =0A= cases to be decided (three possibilities for each, with the case where = both are equal eliminated) and thus=0A= there are different types of graph products that can be = defined. =0A= =0A=

=0A= The most commonly used graph products, given by conditions sufficient = and necessary for adjacency, are summarized in the=0A= following table (Hartnell and Rall 1998). Note that the terminology is = not quite standardized, so these products may=0A= actually be referred to by different names by different sources (for = example, the graph = lexicographic product is=0A= also known as the graph = composition; Harary 1994, p 21). Many other graph products can = be found in Jensen and=0A= Toft (1994).=0A= =0A=

=0A=

=0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A=
graph product namesymboldefinition
graph = Cartesian Product ( and =0A= =0A= ) or (=0A= =0A= and )
graph = categorical Product (=0A= =0A= and =0A= =0A= )
graph = lexicographic product (=0A= =0A= ) or ( and =0A= =0A= )
graph strong = product ( and =0A= =0A= ) or (=0A= =0A= and ) or (=0A= =0A= and =0A= =0A= )
=0A=
=0A=

=0A= =0A=

=0A= Graph Cartesian Product, Graph Categorical Product, Graph Composition, Graph Lexicographic Product, = Graph Strong Product, Graph Sum=0A= =0A=

=0A= =0A=

=0A=
=0A=

=0A= References=0A= =0A=

=0A= =0A=

=0A= Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.=0A=

=0A= Hartnell, B. and Rall, D. "Domination in Cartesian Products: = Vizing's Conjecture." In=0A= Domination in Graphs--Advanced Topics (Ed. = T. W. Haynes, S. T. Hedetniemi, and = P. J. Slater).=0A= New York: Dekker, pp. 163-189, 1998.

=0A= Jensen, T. R. and Toft, B. Graph Coloring Problems. New York: Wiley, 1994.=0A=

=0A= =0A=

=0A= =0A= =0A=

=0A= =0A=

=0A= =0A=

=0A=
=0A= =0A=

=0A= =0A= =0A= =0A= Author: Eric W. Weisstein
=0A= © 1999-2003 Wolfram Research, = Inc.
=0A= =0A= =0A=

=0A=
=0A= =0A= =0A= =0A=

3D""


=0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A= =0A=
=0A= 3D"header"=0A=
=0A= 3D"logo"=0A= =0A= 3D"logo"=0A=
=0A= =0A=


=0A=

=0A=

=0A= =0A= =0A= =0A= =0A= ------=_NextPart_000_0063_01C2BD49.878AD480--