Graph Product

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

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

Graph products can be computed using the unsupported and undocumented Wolfram Language function GraphComputation`GraphProduct[G, H, type].

graph product name	symbol	definition
graph Cartesian product		( and ) or ( and )
graph categorical product		( and )
graph lexicographic product		() or ( and )
graph strong product	{{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]H" src="https://mathworld.wolfram.com/images/equations/GraphProduct/Inline24.svg" style="height:22px; width:52px" />	( and ) or ( and ) or ( and )

---

REFERENCES

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

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

Imrich, W.; Klavzar, S.; and Rall, D. F. Graphs and their Cartesian Product. Wellesley, MA: A K Peters, 2008.Jensen, T. R. and Toft, B. Graph Coloring Problems. New York: Wiley, 1994.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم صناعة الشبابيك يشرع بإدامة شباكين قديمين لمرقد الإمامين العسكريين (عليهما السلام)

فرقة العباس (عليه السلام) تختتم خدماتها المقدمة للزائرين في سامراء

موكب العتبتين المقدستين يحيي ذكرى استشهاد الإمام الهادي (عليه السلام) في سامراء

العتبة العسكرية المقدسة تكرّم وفد العتبة العباسية المقدسة لمشاركته في تقديم الخدمات للزائرين

المزيد

الآخبار الصحية

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

الآخبار التكنلوجية

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength