## 1009 Reputation

5 years, 174 days
changsha, China

## Some comments on the products of two gra...

It is found in [1] that there are 256 possible products of any two graphs using the adjacency and the non-adjacency relations of these graphs.  I think all these products can be handled with the function RelationGraph by Carl Love.

```sum(binomial(8, i),i=0..8)#Make a choice in each item, i.e., 2^8=256
```

[1] Barik, S., Bapat, R.B., Pati, S.: On the Laplacian spectra of product graphs. Appl. Anal. Discrete Math. 9, 39–58 (2015)

Out of these, four graph products namely, the Cartesian product (condition 1 or condition 7), the direct product (condition 3), the strong product (condition 1 or condition 3 or condition 7) and the lexicographic product (condition 1 or condition 3 or condition 5 or condition 7) are known as the standard graph products and have been studied by many researchers.

Here the conormal product is given by choosing the condition 1 or condition 3 or  condition 4 or  condition 5 or condition 7. It chooses “condition 4” more than the lexicographic product.

Therefore, the problems of computing products of two graphs in the future can be regarded as variants of the same problem on the mapleprimes, if not discussing the efficiency problem.

## I would like to give a specific example....

You say in the post:

Give graph G1 and a graph G2  the problem is to extract maximum isomorphic copies of G1 from G2 such that it has no edge intersection maximum number is floor((number of edges of G2)/(number of edges of G1))...

I wonder if you missed a full-stop in that sentence. Is it supposed to be:

Give graph G1 and a graph G2  the problem is to extract maximum isomorphic copies of G1 from G2 such that it has no edge intersection. Maximum number is floor((number of edges of G2)/(number of edges of G1))...

or:

Give graph G1 and a graph G2  the problem is to extract maximum isomorphic copies of G1 from G2 such that these isomorphic copies of G1 are edge-disjoint in G2

I gave you an example, and please check if I understand correctly.

We can find at most three copies of G1 in G2 that are edges disjoint. Is "3" the answer you want?

I'm very interested in whether your C++ program can handle this example I'm talking about?

## Give some examples...

Can you give some examples for illustrating the subgraphs you are looking. I didn't catch your definition.

For example, you say:

• it has no edge intersection maximum number is floor((number of edges of G2)/(number of edges of G1)) ..

What is edge intersection mximum number?

## How to view the improvements of Maple 20...

@Carl Love  Nice!  But where can we see Maple's improvements in some basic functions, such as "local" here? I checked the help documentation for  functions "proc" or "local" and there was no mention of improvements in maple 2022.

## There seems to be no problem...

@vs140580 I downloaded your worksheet (the codes were contributed by Carl Love), it runs without any problem on my side.

## Thanks!...

@Carl Love Thanks for informing that this is a extremely nonstandard numeric output format. Yes, as  tomleslie  said, this was entered manually by me, giving a bad example.

## cat...

@tomleslie I just saw that cat might be able to do that.  I am so glad you have reminded me.

## Intermediate expression...

@tomleslie Thanks! What if the expression is derived from an intermediate derivation instead of the original input? If the expression is very long, I might not want to copy it again. I'd like to store it directly in my txt files.

## increase the size of vertices?...

@vs140580 I don't understand what you mean by that.

You say:

•  I need to see the vertex a big labels , edges how they are moving exactly in the graph more clearly which edge is exactly from which vertex to which after converting to pdf.

Do you mean to increase the size of the vertices and  thier labels ? The PDF generated by Gephi is a vector image, and you can resize  it without distortion.

F_0F_1_3.pdf

## A concrete example...

@vs140580 I am not familiar with the algorithmic problem of how to generate a connected planar graph. I am also a beginner in ogdf. So far I haven't learned how to build it locally (Windows).

I recently learned that python seems to provide the interface (https://pypi.org/project/ogdf-python/), but again,  it need source codes of ogdf to build it locally. (I haven't seen a detailed step by step process for building ogdf for windows).  But no matter how, you can click on the link  (ogdf-python) . Then enter the following code I wrote.

```# uncomment if you didn't set this globally:
# %env OGDF_BUILD_DIR=~/ogdf/build-debug
from ogdf_python import ogdf, cppinclude
cppinclude("ogdf/basic/graph_generators/randomized.h")
cppinclude("ogdf/planarity/PlanarizationLayout.h")

G = ogdf.Graph()
ogdf.setSeed(1)
ogdf.randomPlanarConnectedGraph(G, 10, 15)
GA = ogdf.GraphAttributes(G, ogdf.GraphAttributes.all)
for n in G.nodes:
GA.label[n] = "a%s" % n.index()

SL = ogdf.PlanarizationLayout()
SL.call(GA)
ogdf.GraphIO.drawSVG(GA, "sugiyama-simple.svg")
GA```

As for how Maple calls it, I don't know yet. Maybe I'll learn it in the future.

ogdf is a self-contained `C++` library for graph algorithms, in particular for (but not restricted to) automatic graph drawing. It offers sophisticated algorithms and data structures to use within your own applications or scientific projects.

## randomPlanarConnectedGraph()

 void ogdf::randomPlanarConnectedGraph ( Graph & G, int n, int m )

Creates a random connected (simple) planar (embedded) graph.

Parameters
 G is assigned the generated graph. n is the number of nodes of the generated graph. m is the number of edges of the generated graph.
Note
`n` has a lower bound of 1, and `m` has a lower bound of `n` and an upper bound of \(3n-6\). The supplied values are adjusted if they are out of these bounds.

## A small application...

@Carl Love Thank you so much.  A small application is the rewriting of the function of the k-power of a graph.

```gpower:=proc(g,k)
local verticesofg;
verticesofg:=GraphTheory:-Vertices(g):
RelationGraph(
proc(a,b)
local dis;
dis:= GraphTheory:-Distance(g,a,b);
dis<=k and  dis<>0;
end proc,
verticesofg)
end proc

s:=gpower(PathGraph(10),2);DrawGraph(s)
s := `Graph 4: an undirected unweighted graph with 10 vertices and 17 edge(s)`
```

Edit: Sorry, I didn't notice that you had written down the powers of a graph.  Sure, your unions algorithm is faster.

## @Carl Love Thank you.  It...

@Carl Love Thank you.  It's almost late at night here, and I don't have my computer with me. So I can't feel your wonderful code yet. But I am fully convinced that it is correct. As far as the lexicographic product is concerned, I am probably more interested in the panning implementation of RelationGraph in maple. Maybe it's not always the most effective. But it can reflect the degree of abstraction of certain graph operations. And not just some graph operations in isolation.

## they are different...

@tomleslie By definition, lexicographic product and cartesian product are different binary operations on graphs. The cartesian product of G and H is a subgraph of the lexicographic product of G and H.

The difference between them lies in the following restrictions.

Cartesian product:

•  iff u1 is adjacent to u2 and v1 = v2

lexicographic product:

•  iff u1 is adjacent to u2

The lexicographic product is also known as graph substitution, since lexicographic product of G  and H  can be obtained from G by substituting a copy Hu of H for every vertex u of G and then joining all vertices of Hu with all vertices of Hv if  uv in  E(G).

 4 5 6 7 8 9 10 Last Page 6 of 16
﻿