Strong product of graphs
Encyclopedia
In graph theory
, the strong product G ⊠ H of graphs G and H is a graph such that
The tensor product is also called the normal product and AND product. It was first introduced by Sabidussi
in 1960. László Lovász
showed that Lovász theta function
is multiplicative:
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the strong product 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,u') and (v,v') are adjacent in G × H if and only ifIf and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
u' is adjacent with v' or u'=v' , and u is adjacent with v or u = v.
The tensor product is also called the normal product and AND product. It was first introduced by Sabidussi
Gert Sabidussi
Gert Sabidussi is an Austrian-Canadian mathematician specializing in combinatorics and graph theory.- Biography :...
in 1960. László Lovász
László Lovász
László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
showed that Lovász theta function
Lovász number
In graph theory, Lovász number of a graph is a real number that is an upper bound on the Shannon capacity of the graph. It is also known as Lovász theta function and is commonly denoted by ϑ...
is multiplicative: