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
15 views

Converting all arcs to polygonal arcs in a plane graph

I am trying to understand a proof on the conversion of arcs to polygonal arcs in plane graphs, in the book "Graphs on Surfaces" by Mohar and Thomassen. In the book, an arc joining two points $x,y \in ...
1
vote
1answer
10 views

Vertex deletion and chromatic number proof

Let G be a graph such that, for all vertices $a$ and $b$, $\chi(G-${$a-b$}$)=\chi(G)-2$. Prove that G is a complete graph. I started by drawing $K_5$ which has chromatic number $\chi(K_5)=5$ and ...
2
votes
1answer
19 views

How to get the directed line graph of the complete digraph?

When we replace every edge of the complete graph $K_N$ by a pair of directed edges, we get a complete directed graph, the Complete DiGraph $DK_N$ . Let $DL_{N}$ be directed line graph of the complete ...
0
votes
0answers
12 views

The Three Ways to Arrange Squares in Barnette Graphs

Below you see an example of a bicubic graph consisting of faces with degree $4$ and $6$, which makes up the set of graphs of my interest and is a subset of the so called Barnette graphs. ...
2
votes
1answer
41 views

How to draw that graph?

A specific set of graphs was given here: Let $G$ be a 3-regular connected planar graph with a planar embedding where each face has degree either 4 or 6 and each vertex is incident with exactly one ...
1
vote
1answer
17 views

Finding the longest path in a directed graph where each node can be visited $N$ times?

I've read that the longest path problem is $NP$-Hard, but what about where it is specified that each node can be visited a maximum of $N$ times? It seems the longest-path problem is a special case of ...
0
votes
1answer
17 views

example of a graph such that K(G)=δ(G)=Δ(G)E(G)

example of a graph such that K(G)=δ(G)=Δ(G), where K(G) is the number of components,δ(G) is the minimum degree of G and Δ(G) is the maximum degree in G.
0
votes
1answer
14 views

A finite, undirected, connected and simple graph with Eulerian circuit has $3$ vertices with the same degree

Let $G=(V,E)$ a finite, undirected, connected and simple graph, $|V| \ge 3. \space$ Prove: If $G$ has Eulerian circuit then $G$ has $3$ vertices with the same degree.
0
votes
0answers
11 views

Cuts in planar graphs

I am currently trying to prove the correspondence between cuts of a planar graph $G$ and the even sets of its dual, $G^*$. An even set $D\subseteq E$ is such that all vertices of $G^*$ are incident ...
2
votes
1answer
38 views

Number of faces in a planar graph bounded by odd length cycles?

Suppose that every face in a planar graph is bounded by odd length cycles, then the number of faces of this planar graph is even. I want to prove this using Euler's formula, but not really sure where ...
0
votes
1answer
32 views

What is the terminology for assigning $K_{m_i}$ (complete graph) to the $i$ th vertex, 'joining' if the corresponding vertices are adjacent?

Given a connected graph $G$ with $n$ vertices and given set of $\{m_1,m_2,...,m_n\}$ $n$ integers, we form a new graph $G^$ by considering the complete graph $K_{m_i}$ for each vertex i and 'join' ...
0
votes
2answers
22 views

Prove that if G contains an odd vertex then every vertex of G is odd

Let G be a graph with degree of each vertex either $m$ or $n$, where there are $m$ vertices of degree $m$ and $n$ vertices of degree $n$. Prove that if G contains an odd vertex then every vertex of G ...
0
votes
0answers
16 views

Probability of maximum degree in On random graphs I by Erdos

In The Maximum Degree of a Random Graph by RIORDAN et al., the authors commented that the study of the distribution of the maximum degree $d^{max}(G)$ of a random graph $G$ was started by Erdos and ...
0
votes
1answer
31 views

Confused with the power set of an integer

I am going through The Maximum Degree of a Random Graph by RIORDAN et al. On the second page, the notation $\mathbb{P}(\mathcal{D})$ is used which I assume the power set of the set $\mathcal{D}$. ...
0
votes
0answers
34 views

Here is a question on combinatorics [on hold]

here are ten items on sale at a bazaar, each costing less than one dollar. Prove that it is possible for two people to purchase distinct subsets of these objects and pay exactly the same amount. (Not ...
1
vote
1answer
46 views

Graph Theory Proof of Website Clicks [on hold]

Suppose we have n websites such that for every pair of websites $A$ and $B$, either $A$ has a link to $B$ or $B$ has a link to $A$. Prove or disprove that there exists a website that is reachable from ...
0
votes
1answer
28 views

Spectrum of k-partite graph

For a given undirected graph, it is known that the signless Laplacian $Q=D+W$ is positive semidefinite, where $W$ is the adjacency matrix and $D$ is the degree matrix. In particular, the smallest ...
0
votes
0answers
16 views

Matching as an induced subgraph

Let $G = (V, E)$ be a bipartite graph. Say $V'$ induces a $k$-matching if $G[V']$ has $2k$ vertices and $k$ edges such that every connected component contains two vertices. Does a graph $G$ wich ...
6
votes
0answers
26 views

Chromatic Number of Circulant Graph

Consider the Circulant Graph $Ci_{2n}(1,n-1,n)$ as described here: http://mathworld.wolfram.com/MusicalGraph.html Another way to describe $Ci_{2n}(1,n-1,n)$ would be $2n$ vertices with vertex set ...
0
votes
0answers
36 views

A simple proof for Erdos-Gallai's theorem

According to Erdos-Gallai's theorem we have this inequality : $\sum_{i=1}^k d_i \le k(k-1) + \sum_{i=k+1}^n min(d_i,k)$ which is used to show if a graph exists with a given degree sequence. ( $ 1 ...
0
votes
1answer
18 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 ...
0
votes
0answers
14 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 ...
0
votes
0answers
18 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 ...
2
votes
0answers
27 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
30 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
9 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
15 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
4 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
30 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
8 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.
2
votes
0answers
17 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 ...
2
votes
0answers
19 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 ...
2
votes
1answer
35 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
0answers
30 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
1answer
21 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 ...
0
votes
0answers
9 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
1
vote
0answers
22 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
1answer
26 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 ...
4
votes
1answer
54 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. ...
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?
1
vote
1answer
21 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 ...
2
votes
1answer
39 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 ...
1
vote
2answers
37 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 ...
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
63 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 ...
0
votes
1answer
27 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
49 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
0answers
29 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.