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.

learn more… | top users | synonyms

0
votes
0answers
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 ...
3
votes
1answer
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 ...
-3
votes
1answer
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$ ...
0
votes
0answers
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$ ...
0
votes
1answer
41 views

Determine Ramsey number of(2k2,3k2)

I am having trouble finding the Ramsey number of $2\times$(complete graph of 2 vertices) and $3\times$(the complete graph of two vertices). Any help would be appreciated. Don't really understand if $...
0
votes
1answer
29 views

Graph theory , mathematics

I have one problem. Graph theory: Prove that in bipartite graph $G=(X,Y,E)$ where $1 \le |X| \le |Y|$ and $\min \deg \ge \frac{(|{X}|+1)}{2}$ , each two vertices from $Y$ have the common vertices. ...
0
votes
1answer
22 views

Finding an MST among all spanning trees with maximum of white edges

Let an undirected graph $G=(V,E)$ with the color property $c(e)$ for every edge (could be black or white) and a weight property $1 \le w(e) \le 100$. Find the MST from the set of all spanning trees ...
1
vote
0answers
31 views

What infos can I get from an adjacency matrix of a graph?

So I have this matrix for the multigraph G \begin{matrix} 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 2 & 1 & 0 & 0 \\ ...
2
votes
1answer
33 views

A correct expression for Hardness?

I'm interested in whether it's possible to express the hardness of a result in the following form. 1.For example: Suppose $A(n)$ is the class of graphs for which the minimum degree $\delta(G)\geq n/...
2
votes
1answer
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$. ...
0
votes
1answer
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?
1
vote
1answer
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 ...
1
vote
1answer
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
0
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
35 views

Number of labeled trees with a certain condition

I was wondering about that one: A "varied Tree" T is a tree where for each 2 distinct vertices (non-leaves) u,v $ deg(u) \neq deg(v)$. How many varied trees are there for the set of vertices $\{1,...
0
votes
0answers
20 views

Find a set of vertices $U\subseteq V$ included in some simple cycle

Let $G=(V,E)$, an un-directed graph. Find an efficient algorithm to return a $U\subseteq V$, where $u\in U$ is in some simple cycle of $G$. So basically we've learned in class about the $low$ ...
0
votes
1answer
20 views

Approximate perfect matching through MST

If I compute a minimum spanning tree T in a graph with an even number of vertices and T contains a perfect matching M (which is unique in this case), can I get some approximation guarantee on the ...
2
votes
1answer
119 views

Unique Trianlge Count sequence

Consider a simple graph $G(V,E)$, such that $V = \{1,2,\dots, n\}$. We can define the triangle count of a vertex as follows: $\Delta(v) = $ Number of triangles in the graph such that $v$ is one of ...
1
vote
1answer
35 views

What is a rotation system of a plane graph?

I have this question on an exam. I just need explanation on what's meant by rotation system? Below is the rotation system of a plane graph. 0: -> 6 -> 2 1: -> 4 -> 3 2: -> 0 -> 4 -> 5 3: -> 4 -> ...
1
vote
3answers
81 views

Full binary tree theorem proof validity?

I'm reviewing some of the theorems that make up the Full binary tree theorem and want to make sure my proof for how the number of internal nodes $I$ is related to the number of total nodes $N$ is ...
3
votes
1answer
24 views

prove graph G with n vertices, vertex of degree $n-1$ and rest of the vertices of degree $1$ is a tree graph

I'm a discrete math student and I've bumped into the following question. I tried to prove it and specifically in first part I thought of two ways of proving it. but in each of the ways the proof looks ...
4
votes
0answers
45 views

Proof verification: Mantel's theorem

if a graph $G=(V,E)$ on $n$ vertices contains no triangles than it contains at most $n^2/4$ edges. Proof: Let v$\in$V be a vertex of maximum degree k. since G contains no triangles, there are no ...
1
vote
0answers
31 views

What are “boundaries” (as defined here) really called and where can I learn more?

My guess is that boundaries (perhaps under a different name) in graph theory are probably defined like this: Definition 0. Let $G$ denote a graph, $A$ denote a subset of $G$. Then a candidate ...
1
vote
1answer
41 views

Prove or disprove the law of double pseudo-complements hold for subgraphs?

As for the categories of subgraphs of a given graph $X$ with their inclusions, we have a co-Heyting algebra (and Heyting algebra). In the co-Heyting algebra, we define $\sim$$A$ as the pseudo-...
0
votes
1answer
23 views

Covering a uniform hypergraph with complete $r$-partite hypergraphs

In combinatorial terms, I was wondering how many complete $r$-partite $k$-uniform hypergraphs are needed to cover the edges of the complete $n$-vertex $k$-uniform hypergraph $\binom{[n]}{k}$. An $r$-...
1
vote
1answer
27 views

How to give a formula of the perimeter of a $r$-neighborhood of a smooth set in $2D$?

Let $A$ be a simply connected open set in $\mathbb{R}^2$ with smooth boundary. Define $$A^r := \{x \in \mathbb{R}^2: d(x, A) \le r \},$$ where $d$ is the distance function. Let $P$ denote the ...
3
votes
4answers
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 ...
2
votes
2answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
1answer
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.
1
vote
0answers
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 ...
0
votes
1answer
28 views

Known results on the relationship between automorphisms and spectrum of a graph?

I recently saw this post from Ed Pegg on Math Stack Exchange about integral graphs with trivial automorphism groups. I am interested in trying to construct smaller such graphs - at the very least, I ...
0
votes
1answer
43 views

Number of graphs having a specific structure

Let $\mathcal{N} = \{1,2,\ldots,N\}$ and $\mathcal{N}^i = \mathcal{N}\setminus \{i\} $. For each $i \in \mathcal{N}$ and for each $S \subset \mathcal{N}^i$, we have a vertex $C_i^S$. For example, if $...
1
vote
1answer
41 views

Random walk on a connected graph

I am reading a book and I have a problem understanding why a relation holds. Assume that we have a time-homogeneous random walk on a connected graph $G=(V,E)$. For $o\in V$, the roundtrip from $o$ ...
1
vote
1answer
21 views

Surjective homomorphism preserves planarity?

I was just wondering if for surjective homomorphism of G to H, where G is planar hold that H is planar as well. This is clearly false for non-surjective ones, but for surjective? How it is with ...
2
votes
2answers
52 views

Looking for an algorithm to generate int 0- 255 when provided with an arbitrary pair of numbers between 1 - 99 (upper limit can be you your choice)

This is intended to uniquely number the links between a mesh of an arbitrary number o nodes (for my needs anywhere between 1 and 50 is OK. The upper limit can be your choice as long as it is higher ...
3
votes
1answer
68 views

Team grouping troubles

Imagine there are 12 teams, numbered 1 through 12. There are 10 games those teams can compete in, with two teams needed per game. There are 10 rounds, and it is important that after the 10 rounds are ...
2
votes
1answer
41 views

A connected $k$-regular graph of order 12 is embedded in the plane, resulting in eight regions. [closed]

A connected $k$-regular graph of order $12$ is embedded in the plane, resulting in eight regions. What is $k$?
3
votes
1answer
25 views

What is the term of a component drawn surrounded by another component?

Having a drawing (see image) of an undirected graph $G=(V,E)$ where $V = \{A,B,C,D,E,F,G\}$ and $v \in V$ $E = \{\{A,B\},\{B,C\},\{C,D\},\{D,A\},\{D,E\},\{E,F\},\{F,G\},\{G,E\}\}$ each vertex $v$ ...