74 min
- Source: Graph product
In graph theory, a graph product is a binary operation on graphs. Specifically, it is an operation that takes two graphs G1 and G2 and produces a graph H with the following properties:
The vertex set of H is the Cartesian product V(G1) × V(G2), where V(G1) and V(G2) are the vertex sets of G1 and G2, respectively.
Two vertices (a1,a2) and (b1,b2) of H are connected by an edge, iff a condition about a1, b1 in G1 and a2, b2 in G2 is fulfilled.
The graph products differ in what exactly this condition is. It is always about whether or not the vertices an, bn in Gn are equal or connected by an edge.
The terminology and notation for specific graph products in the literature varies quite a lot; even if the following may be considered somewhat standard, readers are advised to check what definition a particular author uses for a graph product, especially in older texts.
Even for more standard definitions, it is not always consistent in the literature how to handle self-loops. The formulas below for the number of edges in a product also may fail when including self-loops. For example, the tensor product of a single vertex self-loop with itself is another single vertex self-loop with
E
=
1
{\displaystyle E=1}
, and not
E
=
2
{\displaystyle E=2}
as the formula
E
G
×
H
=
2
E
G
E
H
{\displaystyle E_{G\times H}=2E_{G}E_{H}}
would suggest.
Overview table
The following table shows the most common graph products, with
∼
{\displaystyle \sim }
denoting "is connected by an edge to", and
≁
{\displaystyle \not \sim }
denoting non-adjacency. While
≁
{\displaystyle \not \sim }
does allow equality,
≄
{\displaystyle \not \simeq }
means they must be distinct and non-adjacent. The operator symbols listed here are by no means standard, especially in older papers.
In general, a graph product is determined by any condition for
(
a
1
,
a
2
)
∼
(
b
1
,
b
2
)
{\displaystyle (a_{1},a_{2})\sim (b_{1},b_{2})}
that can be expressed in terms of
a
n
=
b
n
{\displaystyle a_{n}=b_{n}}
and
a
n
∼
b
n
{\displaystyle a_{n}\sim b_{n}}
.
Mnemonic
Let
K
2
{\displaystyle K_{2}}
be the complete graph on two vertices (i.e. a single edge). The product graphs
K
2
◻
K
2
{\displaystyle K_{2}\square K_{2}}
,
K
2
×
K
2
{\displaystyle K_{2}\times K_{2}}
, and
K
2
⊠
K
2
{\displaystyle K_{2}\boxtimes K_{2}}
look exactly like the graph representing the operator. For example,
K
2
◻
K
2
{\displaystyle K_{2}\square K_{2}}
is a four cycle (a square) and
K
2
⊠
K
2
{\displaystyle K_{2}\boxtimes K_{2}}
is the complete graph on four vertices.
The
G
1
[
G
2
]
{\displaystyle G_{1}[G_{2}]}
notation for lexicographic product serves as a reminder that this product is not commutative. The resulting graph looks like substituting a copy of
G
2
{\displaystyle G_{2}}
for every vertex of
G
1
{\displaystyle G_{1}}
.
See also
Graph operations
Notes
References
Kata Kunci Pencarian:
- Graph database
- Globalisasi
- Lee Min-ho (pemeran)
- Meta Platforms
- Daftar fitur Facebook
- Penyusutan gletser sejak 1850
- Daftar masalah matematika yang belum terpecahkan
- Canberra
- Graph product
- Cartesian product of graphs
- Tensor product of graphs
- Rooted product of graphs
- Product
- Strong product of graphs
- Graph operations
- Graph (discrete mathematics)
- Planar graph
- Lexicographic product of graphs
No More Posts Available.
No more pages to load.
