Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

asked 2022-07-15 04:51:31 +0200

licheng gravatar image

Is there code to identify a decomposition of the lexicographic product of the graph

In graph theory, the lexicographic product or (graph) composition G ∙ H of graphs G and H is a graph such that

  • the vertex set of G ∙ H is the cartesian product V(G) × V(H); and
  • any two vertices (u,v) and (x,y) are adjacent in G ∙ H if and only if either u is adjacent with x in G or u = x and v is adjacent with y in H.

Recognition problem Given a graph G, can we guess whether there exist graphs G_1,...,G_k such that G=G_1 ∙ ⋯ ∙G_k ?

For the Cartesian product of graphs, this problem can be solved by the following code.

from sage.graphs.graph_decompositions.graph_products import is_cartesian_product
g = graphs.PetersenGraph()
is_cartesian_product(g)

False

g = graphs.Grid2dGraph(5,5)
g.relabel()
b,D = g.is_cartesian_product(g, relabeling=True)
b
D

True {0: (0, 20), 1: (0, 15), 2: (0, 10), 3: (0, 5), 4: (0, 0), 5: (1, 20), 6: (1, 15), 7: (1, 10), 8: (1, 5), 9: (1, 0), 10: (2, 20), 11: (2, 15), 12: (2, 10), 13: (2, 5), 14: (2, 0), 15: (3, 20), 16: (3, 15), 17: (3, 10), 18: (3, 5), 19: (3, 0), 20: (4, 20), 21: (4, 15), 22: (4, 10), 23: (4, 5), 24: (4, 0)}

For the above codes, we refer to the links below. [https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_decompositions/graph_products.html]

Similarly, is there any codes for the lexicographic product decomposition of graphs.

Is there code to identify a decomposition of the lexicographic product of the graph

In graph theory, the lexicographic product or (graph) composition G ∙ H of graphs G and H is a graph such that

  • the vertex set of G ∙ H is the cartesian product V(G) × V(H); and
  • any two vertices (u,v) and (x,y) are adjacent in G ∙ H if and only if either u is adjacent with x in G or u = x and v is adjacent with y in H.

Recognition problem Given a graph G, can we guess whether there exist graphs G_1,...,G_k such that G=G_1 ∙ ⋯ ∙G_k ?

For the Cartesian product of graphs, this problem can be solved by the following code. funtion is_cartesian_product.

from sage.graphs.graph_decompositions.graph_products import is_cartesian_product
g = graphs.PetersenGraph()
is_cartesian_product(g)

False

g = graphs.Grid2dGraph(5,5)
g.relabel()
b,D = g.is_cartesian_product(g, relabeling=True)
b
D

True {0: (0, 20), 1: (0, 15), 2: (0, 10), 3: (0, 5), 4: (0, 0), 5: (1, 20), 6: (1, 15), 7: (1, 10), 8: (1, 5), 9: (1, 0), 10: (2, 20), 11: (2, 15), 12: (2, 10), 13: (2, 5), 14: (2, 0), 15: (3, 20), 16: (3, 15), 17: (3, 10), 18: (3, 5), 19: (3, 0), 20: (4, 20), 21: (4, 15), 22: (4, 10), 23: (4, 5), 24: (4, 0)}

For the above codes, we refer to the links below. [https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_decompositions/graph_products.html]

Similarly, is there any codes for the lexicographic product decomposition of graphs.

Is there code to identify a decomposition of the lexicographic product of the graph

In graph theory, the lexicographic product or (graph) composition G ∙ H of graphs G and H is a graph such that

  • the vertex set of G ∙ H is the cartesian product V(G) × V(H); and
  • any two vertices (u,v) and (x,y) are adjacent in G ∙ H if and only if either u is adjacent with x in G or u = x and v is adjacent with y in H.

Here's what I thought about.

Recognition problem Given a graph G, can we guess whether there exist graphs G_1,...,G_k such that G=G_1 ∙ ⋯ ∙G_k ?

For the Cartesian product of graphs, this problem can be solved by the funtion is_cartesian_product.

from sage.graphs.graph_decompositions.graph_products import is_cartesian_product
g = graphs.PetersenGraph()
is_cartesian_product(g)

False

g = graphs.Grid2dGraph(5,5)
g.relabel()
b,D = g.is_cartesian_product(g, relabeling=True)
b
D

True {0: (0, 20), 1: (0, 15), 2: (0, 10), 3: (0, 5), 4: (0, 0), 5: (1, 20), 6: (1, 15), 7: (1, 10), 8: (1, 5), 9: (1, 0), 10: (2, 20), 11: (2, 15), 12: (2, 10), 13: (2, 5), 14: (2, 0), 15: (3, 20), 16: (3, 15), 17: (3, 10), 18: (3, 5), 19: (3, 0), 20: (4, 20), 21: (4, 15), 22: (4, 10), 23: (4, 5), 24: (4, 0)}

For the above codes, we refer to the links below. [https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_decompositions/graph_products.html]

Similarly, is there any codes code for the lexicographic product decomposition of graphs.

Is there code to identify a decomposition of the lexicographic product of the graph

In graph theory, the lexicographic product or (graph) composition G ∙ H of graphs G and H is a graph such that

  • the vertex set of G ∙ H is the cartesian product V(G) × V(H); and
  • any two vertices (u,v) and (x,y) are adjacent in G ∙ H if and only if either u is adjacent with x in G or u = x and v is adjacent with y in H.

Here's what I thought about.

Recognition problem Given a graph G, can we guess whether there exist graphs G_1,...,G_k such that G=G_1 ∙ ⋯ ∙G_k ?

For the Cartesian product of graphs, this problem can be solved by the funtion is_cartesian_product.

from sage.graphs.graph_decompositions.graph_products import is_cartesian_product
g = graphs.PetersenGraph()
is_cartesian_product(g)

False

g = graphs.Grid2dGraph(5,5)
g.relabel()
b,D = g.is_cartesian_product(g, relabeling=True)
b
D

True {0: (0, 20), 1: (0, 15), 2: (0, 10), 3: (0, 5), 4: (0, 0), 5: (1, 20), 6: (1, 15), 7: (1, 10), 8: (1, 5), 9: (1, 0), 10: (2, 20), 11: (2, 15), 12: (2, 10), 13: (2, 5), 14: (2, 0), 15: (3, 20), 16: (3, 15), 17: (3, 10), 18: (3, 5), 19: (3, 0), 20: (4, 20), 21: (4, 15), 22: (4, 10), 23: (4, 5), 24: (4, 0)}

For the above codes, we refer to the links below. [https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_decompositions/graph_products.html]

Similarly, is there any code for the lexicographic product decomposition of graphs.

Is there code to identify a decomposition of the lexicographic product of the grapha graph?

In graph theory, the lexicographic product or (graph) composition G ∙ H of graphs G and H is a graph such that

  • the vertex set of G ∙ H is the cartesian product V(G) × V(H); and
  • any two vertices (u,v) and (x,y) are adjacent in G ∙ H if and only if either u is adjacent with x in G or u = x and v is adjacent with y in H.

Here's what I thought about.

Recognition problem Given a graph G, can we guess whether there exist graphs G_1,...,G_k such that G=G_1 ∙ ⋯ ∙G_k ?

For the Cartesian product of graphs, this problem can be solved by the funtion is_cartesian_product.

from sage.graphs.graph_decompositions.graph_products import is_cartesian_product
g = graphs.PetersenGraph()
is_cartesian_product(g)

False

g = graphs.Grid2dGraph(5,5)
g.relabel()
b,D = g.is_cartesian_product(g, relabeling=True)
b
D

True {0: (0, 20), 1: (0, 15), 2: (0, 10), 3: (0, 5), 4: (0, 0), 5: (1, 20), 6: (1, 15), 7: (1, 10), 8: (1, 5), 9: (1, 0), 10: (2, 20), 11: (2, 15), 12: (2, 10), 13: (2, 5), 14: (2, 0), 15: (3, 20), 16: (3, 15), 17: (3, 10), 18: (3, 5), 19: (3, 0), 20: (4, 20), 21: (4, 15), 22: (4, 10), 23: (4, 5), 24: (4, 0)}

For the above codes, we refer to the links below. [https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_decompositions/graph_products.html]

Similarly, is there any code for the lexicographic product decomposition of graphs.

Is there code to identify a decomposition of the lexicographic product of a graph?

In graph theory, the lexicographic product or (graph) composition G ∙ H of graphs G and H is a graph such that

  • the vertex set of G ∙ H is the cartesian product V(G) × V(H); and
  • any two vertices (u,v) and (x,y) are adjacent in G ∙ H if and only if either u is adjacent with x in G or u = x and v is adjacent with y in H.

Here's what I thought about.

Recognition problem : Given a graph G, can we guess whether there exist graphs G_1,...,G_k such that G=G_1 ∙ ⋯ ∙G_k ?

For the Cartesian product of graphs, this problem can be solved by the funtion is_cartesian_product.

from sage.graphs.graph_decompositions.graph_products import is_cartesian_product
g = graphs.PetersenGraph()
is_cartesian_product(g)

False

g = graphs.Grid2dGraph(5,5)
g.relabel()
b,D = g.is_cartesian_product(g, relabeling=True)
b
D

True {0: (0, 20), 1: (0, 15), 2: (0, 10), 3: (0, 5), 4: (0, 0), 5: (1, 20), 6: (1, 15), 7: (1, 10), 8: (1, 5), 9: (1, 0), 10: (2, 20), 11: (2, 15), 12: (2, 10), 13: (2, 5), 14: (2, 0), 15: (3, 20), 16: (3, 15), 17: (3, 10), 18: (3, 5), 19: (3, 0), 20: (4, 20), 21: (4, 15), 22: (4, 10), 23: (4, 5), 24: (4, 0)}

For the above codes, we refer to the links below. [https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_decompositions/graph_products.html]

Similarly, is there any code for the lexicographic product decomposition of graphs.

click to hide/show revision 7
None

updated 2022-07-17 09:50:39 +0200

dan_fulea gravatar image

Is there code to identify a decomposition of the lexicographic product of a graph?

In graph theory, the lexicographic product or (graph) composition G ∙ H of graphs G and H is a graph such that

  • the vertex set of G ∙ H is the cartesian product V(G) × V(H); and
  • any two vertices (u,v) and (x,y) are adjacent in G ∙ H if and only if either u is adjacent with x in G or u = x and v is adjacent with y in H.

Here's what I thought about.

Recognition problem: Given a graph G, can we guess whether there exist graphs G_1,...,G_k such that G=G_1 ∙ ⋯ ∙G_k ?

For the Cartesian product of graphs, this problem can be solved by the funtion is_cartesian_product.

from sage.graphs.graph_decompositions.graph_products import is_cartesian_product
g = graphs.PetersenGraph()
is_cartesian_product(g)

> False

False

and

 
g = graphs.Grid2dGraph(5,5)
g.relabel()
b,D = g.is_cartesian_product(g, relabeling=True)
b
D
D  

> True
{0: (0, 20),
 1: (0, 15),
 2: (0, 10),
 3: (0, 5),
 4: (0, 0),
 5: (1, 20),
 6: (1, 15),
 7: (1, 10),
 8: (1, 5),
 9: (1, 0),
 10: (2, 20),
 11: (2, 15),
 12: (2, 10),
 13: (2, 5),
 14: (2, 0),
 15: (3, 20),
 16: (3, 15),
 17: (3, 10),
 18: (3, 5),
 19: (3, 0),
 20: (4, 20),
 21: (4, 15),
 22: (4, 10),
 23: (4, 5),
 24: (4, 0)}

True {0: (0, 20), 1: (0, 15), 2: (0, 10), 3: (0, 5), 4: (0, 0), 5: (1, 20), 6: (1, 15), 7: (1, 10), 8: (1, 5), 9: (1, 0), 10: (2, 20), 11: (2, 15), 12: (2, 10), 13: (2, 5), 14: (2, 0), 15: (3, 20), 16: (3, 15), 17: (3, 10), 18: (3, 5), 19: (3, 0), 20: (4, 20), 21: (4, 15), 22: (4, 10), 23: (4, 5), 24: (4, 0)}

For the above codes, we refer to the links below. [https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_decompositions/graph_products.html]below.

https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_decompositions/graph_products.html

Similarly, is there any code for the lexicographic product decomposition of graphs.

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.7.59