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
1answer
13 views

Prove that a graph is complete multipartite iff it has no $k_1 \bigcup k_2$ as a vertex-induced subgraph.

In graph theory, a part of mathematics, a $k$-partite graph is a graph whose vertices are or can be partitioned into $k$ different independent sets. A vertex-induced subgraph (sometimes simply called ...
1
vote
0answers
12 views

Use Gröbner bases to count the $3$-edge colorings of planar cubic graphs…

I found a nice introduction on how to Use Gröbner bases to construct the colorings of a finite graph. Now my graphs $G=(V,E)$ are the line graphs planar cubic graphs, so they are $4$-regular. The ...
0
votes
0answers
5 views

Minimum amount of edges of k-partite subgraph

Let $G$ be a graph with $e$ edges. If $k\geq2$, show that there is a $k$-partite subgraph of G with at least $\lceil\frac{(k-1)e}{k}\rceil$ edges. Can anyone tell me how to start with proving this? ...
0
votes
0answers
10 views

Determining intersection number of $C_n+C_n$ and $\overline{C_n}$.

Is there a method to compute intersection numbers of graphs? For example, I would like to compute the intersection number of $C_n+C_n$ and $\overline{C_n}$, where $C_n$ is the $n-$cycle. I was trying ...
5
votes
1answer
177 views

Euler, Grinberg,… who's next?

Given a cubic planar hamiltonian graph with $F$ faces. Let $a_k$ be the number of face of degree $k$ inside and $b_k$ outside the Hamilton cycle. We have the following: $\sum \limits_k ...
0
votes
0answers
13 views

What is the probability of interpolating the Tutte polynomial of a planar graph from the values at the two hyperbolas?

Crossposted from MO The Tutte polynomial is a bivariate polynomial with positive integer coefficient which is a graph invariant and can be defined recursively. Evaluating it is $\#P$-complete even ...
4
votes
1answer
48 views

2-connected graph problem (West, Introduction to Graph Theory, ex. 4.2.15)

I am struggling with this problem for hours but it seems to be easy. Here is the problem: Proof that every vertex $v$ in 2-connected graph $G$ has neighbour $u$ such that $G - v - u$ is connected. ...
0
votes
0answers
21 views

Is class of graphs with eigenvalue $1$ of any particular importance?

Are graphs with eigenvalue $1$ of multiplicity more than $1$, important one? Please guide me to any book or article discussing such graphs.
2
votes
0answers
22 views

How to read Spectral Theory of Graphs

My background is a course is Linear Algebra -Hoffman,Kunze Graph Theory-Clark. I am reading Spectral Theory of Graphs. My professor has asked me to start from the book Spectra of Graphs by ...
0
votes
0answers
25 views

To show the Petersen graph has $2000$ spanning trees. [on hold]

I want to show that the Petersen graph has $2000$ spanning trees. How can I achieve it?
1
vote
0answers
8 views

Eigenvalue ratio evolution of Laplacian matrix when add edges

Consider an connected digraph, we use the classic definition of the Laplacian matrix $L$: $L=D-A$, where $D$ is the degree matrix and $A$ is the adjacency matrix. There has been many researches on ...
0
votes
0answers
8 views

An efficient algorithm to decide if a directed graph is unilaterally connected

I have been doing practise problems in designing algorithms and came across the following in a past test from an American university (see attached): A directed graph is unilaterally connected if, ...
0
votes
0answers
6 views

Decomposing a graph into $N$ planar sub-graphs that can be drawn on $N$ planes.

I would like to ask you if there is a way for checking if we can decompose a specific graph into $N$ planar sub-graphs that can be drawn on $N$ planes without an edge crossing any of the planes.
0
votes
0answers
3 views

Counting subgraphs of bounded extremal degrees

Let $m\leq n-1$. Is there a closed expression counting the subgraphs of minimum degree $\geq m$ (resp. maximum degree $\geq m$) on $n$ labelled vertices?
1
vote
0answers
15 views

Are there useful visual representations of magmas?

In group theory we have Cayley graphs. Are there analogous or anyway useful visual representations of magma structures? I am unsure about how to construct a graph representing, for instance, a free ...
1
vote
0answers
14 views

“Chemists triple point” in percolation theory

This is a vague question asking about the existence of a mathematical object, instead of properties of a well defined one. I am sorry if this is not the correct forum. I know if you have a random ...
1
vote
1answer
31 views

Does there exist a graph with chromatic number 4 that has no triangle or square cycles?

$K_4$ is an example of a graph that requires 4 colours to be coloured but it contains triangle cycles and a square cycle too. I've tried drawing ever more complicated graphs made up of pentagons, ...
1
vote
1answer
495 views

The complexity of Depth First Search

Can anyone tell me what's the complexity of Depth First Search? I have no idea about what does mean by the complexity.
2
votes
1answer
18 views

Graphs with weighted edges and vertices

I am considering a route planning problem, which I try to model with a graph. I understand that 1. to find a shortest path in a graph, we need to know the weights on the edges. 2. as some places are ...
2
votes
0answers
119 views

Is there matrix representation of the line graph operator?

I had the need to calculate the adjacency matrix $L$ of the line graph of a certain planar $k$-regular graphs $G(n,e)$ ( $n$ vertices and $e=\frac k2 n$ edges) given its adjacency matrix $A_G$. Here I ...
0
votes
0answers
7 views

The random graph quantity $S(n: K, L)$

I am going through Degree sequences of random graphs by Béla Bollobás. On page $3$ the author introduces the quantity $S(n: K, L)$ without any explanation. Could anyone please help me in ...
1
vote
1answer
20 views

Reduction to a max flow problem from a sudoku like puzzle

Given an $n$ by $n$ grid of which some of the squares are black and some are white. I'm allowed to mark some of these squares and the question is to prove whether a given grid with given black squares ...
-2
votes
1answer
24 views

Discrete Math Sequences (Graph or No Graph) [on hold]

Determine if there exists a graph whose degree sequence is the one specified. Draw a graph, or explain why no graph exists. The sequence is 5,4,3,2,1,1
4
votes
1answer
3k views

How to construct the graph from an adjacency matrix?

I have the following adjacency matrix: a b c d a [0, 0, 1, 1] b [0, 0, 1, 0] c [1, 1, 0, 1] d [1, 1, 1, 0] How do I draw the graph, given its adjacency ...
1
vote
1answer
25 views

Number of Labels used in reduction of Isomorphism of Labelled Graph to Graph Isomorphism

From "Lecture Notes in Computer Science" by Christoph M. Hoffmann , Assume that both $X$ and $X'$ have $n$ vertices. We plan to code the graph labels as suitable subgraphs which we attach to the ...
1
vote
0answers
21 views

Small tree containing smaller trees

Given $n$, what is the smallest number $N=N(n)$ with the property that there exists a tree on $N$ (unlabelled) vertices that contains a copy of every tree on $n$ vertices? That such $N$ must exist is ...
1
vote
0answers
48 views

Is it always possible to get MC/DC coverage on an $n$-input Boolean function with $n + 1$ test cases?

In software engineering, there is a coverage metric for testing called modified condition/decision coverage, or MC/DC for short. This metric is well-known in the avionics industry due to showing up in ...
1
vote
2answers
35 views

Connecting up boxes mathematically (Puzzle)

How would you connect each black box once to each colored box without any lines overlapping, this is racking my brain so please help. Note that you can move the boxes where ever you want. Maybe ...
3
votes
1answer
50 views

Colored graph isomorphism reduction to uncolored graph isomorphism

I am trying to find a polynomial time reduction from the colored graph isomorphism to the regular graph isomorphism. Doing a search on this problem, I found this article and it seems like theorem 1 is ...
0
votes
1answer
386 views

Edge weight function for graph instance of scheduling and allocation problem

I have difficulties developing a proper (non-scalar) edge cost function $c_e$ for my resource scheduling problem, which I mapped into a graph problem. Processes $P_i$ need resources $R_i \in ...
2
votes
1answer
38 views

Prove this simple graph is not planar.

Graph I need to show this graph is not planar. I've attempted to find $K_5$ and $K_{3,3}$ as a subgraphs but haven't been successful yet. It's possible but unlikely this graph is planar but I haven't ...
0
votes
1answer
278 views

If $G$ is simple with diameter two and maximum degree $|V(G)| - 2$, then $|E(G)| \geq 2|V(G)| - 4$

This is my try: Because the diameter of $G$ is two and have maximum degree the number of vertex: $|V(G)| - 2$, where $|V(G)|$ is the number of vertex, then the grade for any vertex in $G$ is greater ...
1
vote
1answer
20 views

Graph nomenclature for class-grouped vertices and edges

Is there a name for the subset of graph theory dealing with vertices and edges of distinct classes? For example, I could have a graph in which each vertex must be either blue, yellow or red and each ...
1
vote
0answers
22 views

references of discrete association scheme

I tried to find a book or paper to understanding discrete association scheme but I could not get any book for that. What is the good references for that?
0
votes
0answers
63 views
+50

How to number the left-hand turn paths of planar bicubic graphs?

When you draw a planar cubic bipartite graph $\Gamma$ and 3-color its edges you can use this as an orientation $\mathcal O$. Definition A left-hand turn path on $(\Gamma, \mathcal O)$ is a closed ...
2
votes
3answers
125 views

How Graph Isomorphism is used to determine Graph Automorphism?

From Lecture 2, Algebra and Computation by V. Arvind, (page2,3), I understood below passage- For our graph $G$, let $Aut(G) = H ≤ S_n$. We shall use Weilandt’s notation where $i^\pi$ denotes ...
0
votes
1answer
18 views

How many mappings are there between these two graphs?

Let $P_{20}$ be a path of length 20 like so: $x_0$-$x_1$-$~\cdots~$-$x_{20}$ and $G$ a cycle of order 3. Allegedly there are $3 \cdot 2^{20}$ mappings $P_{20}\rightarrow G$, which I don't quite see. ...
1
vote
1answer
60 views

What kinds of transformations preserve network topology?

I have been reading a number of "network science" papers where the authors perform transformations on networks that seem to preserve the topology of those networks. By "topology", I mean a collection ...
2
votes
2answers
40 views

Unsolved problems in graph theory

Is there a good database of unsolved problems in graph theory?
0
votes
1answer
400 views

What is the difference between `Cross edge` and `Forward edge` in a DFS tree?

In the most general way, Let $G(V, E)$ be a graph, and $T(V', E')$ be the DFS tree of $G$. If an edge $(u, v) \in E'$ is neither a tree edge nor a back edge, How can we determine whether it's a ...
0
votes
1answer
23 views

graphs with smallest eigenvalue at least -1

Let $G$ be an undirected simple graph and let $A$ be its adjacency matrix. It is easy to see that $A$ is neither positive semidefinite nor negative semidefinite. I would like to know if there are ...
1
vote
0answers
28 views

Show that any vertex $v$ of $P$ is half-integral.

Let $G$ be an undirected graph and define $$P=\{x \in R^{V}: x(u)+x(v) \leq 1 \:\:\text{for all edges}\:\: e=uv,\:\: x \geq 0\}$$ Show that any vertex $v$ of $P$ is half integral.
1
vote
1answer
63 views

The set of isomorphisms from a right coset of the automorphism group $Aut(X)$ in $S_n$.

From "Lecture Notes in Computer Science" by Christoph M. Hoffmann , on page 22- Theorem 4 Let $X$ and $X'$ be two isomorphic graphs with vertex set $V = \{1 ..... n\}$ , Then the set of ...
0
votes
2answers
45 views

Large minimal degree of a graph implies that it is connected

Let $G$ be a graph of order n. (a) If $δ(G) ≥ (n−1)/2$, then prove that $G$ is connected. (b) If $δ(G) ≥ (n−2)/2$, then show that $G$ need not be connected. Here $δ(G)$ is the minimal degree ...
0
votes
1answer
13 views

Graph Theory Proof Degree Question

Let G be a graph of order n. Prove that if deg u + deg v ≥ n - 2 for every pair u, v of nonadjacent vertices of G, then G has at most two components.
0
votes
0answers
15 views

Degrees of vertices in a circuit must be even

Let $G$ be a graph with a circuit. Let $C$ denote the subgraph of $G$ consisting of vertices and edges of the circuit. Then for every vertex in $C$, $\deg (v)$ considered in $C$ is even. I would ...
0
votes
2answers
13 views

Removing an edge from a circuit on a connected graph

Let $G = (V,E)$ be a connected graph. Suppose $e$ is an edge in a circuit of $G$. Show that the new graph $(V,E-\{e\})$ is still connected. Attempt: Let $v,w \in V$ be vertices. Then inside $G$, ...
1
vote
1answer
29 views

show that the maximum degree of the graph is 6

Let p1, p2, . . . , pn be n points in the plane such that the distance between any two points is at least one. Let G = (V, E) be the graph such that V = {p1, p2, . . . , pn} and E = {pipj | distance ...
0
votes
1answer
13 views

Calculating the probability of a graph being Erdos-Renyi

Given an undirected, unweighted graph with |V| = 11 and |E|= 19 and given probability p=0.5 I have to calculate the probability of the graph being generated using the Erdos-Renyi Model. I applied the ...
0
votes
0answers
19 views

Does K_4 with an edge removed contain two or three cycles?

I need to answer a question about Cycle Hitting Sets. Such a set if a set that contains at least one edge from every cycles of the graph. My question is. Say we have two adjacent faces. Are there ...