# Tagged Questions

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

33 views

### Application of tensor product of graphs in real life.

I was going through the book HANDBOOK OF PRODUCT GRAPHS by Richard Hammack, Wilfried Imrich, and Sandi Klavzar. In the preface section, application of direct product of graphs is mentioned. I am ...
91 views

### Why are $K_5$ and $K_{3,3}$ the 'cutoffs' for planarity?

I've seen the proof that $K_5$ and $K_{3,3}$ cannot be planar, but I'm curious: is there a why for 5 to be the last complete graph? I have to be honest here, I know very little about Graph Theory. I ...
30 views

### Here is a break-down graph of operations done in 4-bit integer multiplication.

The blue nodes represent the number $b = b_3b_2b_1b_0$, and the green nodes represent the number $a = a_3a_2a_1a_0$. The yellow nodes are the output bits after multiplying $a \cdot b$. If $a\cdot b$ ...
9 views

### Is there a name for this: an even cycle having two smaller even cycles inscribed, linking bipartitions

My apologies for the horribly worded title, I'm not sure how to describe this. Learning about bipartite graphs in discrete math and I noticed this when testing a few cycle graphs. For $n$ even, $C_n$ ...
41 views

49 views

### Shortest path from $s$ to $t$ in a graph with $5$ negative edges and no negative cycles?

Let $G=(V,E)$ a directed and weighted ($w:E\to\mathbb{R}$) and let $s,t\in V$. It is given that there are exactly $5$ negative edges and no negative cycles. Find the shortest path from $s$ to $t$. ...
42 views

### Particular 6-regular graph on 42 vertices. [closed]

Does anybody know of the existence of any known graphs that are 6-regular on 42 vertices?
45 views

### Full binary tree proof validity: Number of leaves $L$ and number of nodes $N$

I'm working through the full binary tree proofs for a blog post I'm writing and I want to make sure I'm not missing anything. This particular proof focuses on relating the number of total nodes $N$ to ...
26 views

### graph theory,problem of graph [closed]

Prove that if dichotomy graph $(X,Y,E)$ is $k$-regular , where $k\geqslant 1 \Rightarrow |X|=|Y|$. Please help me
54 views

### How to solve this Iran TST 2014,second exam, problem？

This Problem is Iran TST 2014, second exam, day 2 ,problem 3 Consider $n$ segments in the plane which no two intersect and between their $2n$ endpoints no three are collinear. Is the following ...
23 views

### Automorphism groups of partially cycle graphs

I define partially cycle graphs as follows. If we add the same subgraph to $n-k$ vertices of an $n$-vertex cycle graph, where $1\le k < n$, we create a partially cycle graph. Here are a few ...
24 views

### Finding number of leaves in a tree of 60 nodes in which 10 are of degree 3

I'm kinda stuck with this and can't seem to solve this question. Let G be a tree with 60 nodes, 10 of those nodes are of degree 3, there are no nodes with a degree larger than 3. How many leaves are ...
21 views

### Translation from math to english – algorithm for generation of graphs with known χ

As I haven’t been able to find such an algorithm implemented I’d like to implement the one from the section 6 of Leighton’s paper¹ myself. I however am not familiar with a notation used in the ...
35 views

53 views

### Finding the number of vertices in a complete graph without finding the roots of a quadratic

I'm taking a class where we are often asked to answer questions like the following: If G is a complete graph with 105 edges, how many vertices does G have? If I were to solve this question, I ...
46 views

### Automorphism on graphs which isn't isomorphic?

So I got the following graph and the Task to determine the Elements of it's automorphism group. The Automorphism is defined as a Graph that is isomorphic to itself. But I think the given Graph isn't ...
21 views

### For every $v\in V$, determine if it belongs to some negative cycle in $G$

Let $G=(V,E)$ a directed graph with a weight function $w:E\to\mathbb{R}$. For every $v\in V$, determine if $v$ belongs to some negative cycle. Obviously we need to utilize Bellman-Ford algorithm for ...
36 views

### How is immortality defined for a digraph?

A presentation on immortality $m$ of a digraph was presented almost as a sink $i\rightarrow m \leftarrow j$ somehow related on conditional independence and markov equivalence classes. I am confused ...
50 views

### Alphabet on homomorphism

So I am trying to learn for an exam, and I found an exercise but without solutions and I can't really get behind the topic: Let $G = (V,E)$ be a connected graph with $v \geq 2$ Vertices. $P(G)$ is ...
27 views

### In graph theory, draw the graph corresponding to the matrix A [closed]

I am studying statistics but decided to have some classes in mathematics. This class is called optimization but apparently, the content is graph theory. This is my first time of taking such class and ...
33 views

### All unique shapes from drawing lines between array of points

I have encountered this problem various times, but have never got my head around it. (I'm not very good in in problems like this...) Please don't blame me for not knowing specific math terms. (I ...
32 views

### Matching in bipartite graph

Every student from a set of students applies for exactly three seminars among the seminars that are offered at their university. Two of the seminars are chosen by exactly 40 students, all others are ...
37 views

### How to describe a set of paths in a graph with as few nodes as possible? [migrated]

I have modeled a problem as a graph that consists of many trees. Some of the nodes in the graph may belong to more than one tree. I am trying to describe a subset of paths in the graph with as few ...
13 views

### What are the properties of non-separating cycle in a genus $g$ surface?

There can be two types of cycle in any genus $g$ surface, separating and non-separating. I know that if the edges of the cycle crosses all the sides of the polygonal schema even number of times then ...
13 views

### how to calculate slack(u,v) in the Edmond's minimum weight matching algorithm (u and v are vertices of a graph)?

I am trying to execute the Edmond's minimum weight matching algorithm. As a reference, I am using a book titled "Combinatorial Optimization Theory and Algorithms" by Bernhard Korte and Jens Vygen. The ...
44 views

### If $G$ and $H$ are two graphs, then what does $G \Delta H$ indicate in graph theory?

I came across this notation in a book titled "Combinatorial Optimization Theory and Algorithms" by Bernhard Korte and Jens Vygen.
39 views

### Proof that there exists a 3d representation of all graphs

Below is a question and proof that I've done. I was wondering if there is a more formal way of concluding a point must exist that is not in a set composed of a finite number planes. Currently I am ...