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

1
vote
1answer
30 views

Show that K and K' cannot both contain an Eulerian trail

For question (b), I understand how to prove that they can't both contain an Eulerian trail--eulerian trail exists if and only if there are no more than 2 odd degrees of the vertices. So for a ...
0
votes
0answers
19 views

Specific type of Eulerian cycle

Suppose i have a 4-regular planar graph, and furthermore suppose i pair the 4 edges incident to each vertex, so if $v \in V$ is adjacent to edges $\{e_{1},e_{2},e_{3},e_{4}\}$ i could for example pair ...
0
votes
0answers
18 views

Graph grouping with geometric criteria

I start with a list of adjacent tetrahedra, where there are tight seals to one another along faces for two tetrahedra that are adjacent. The vertices belonging to these faces for both tetrahedra are ...
0
votes
0answers
32 views

The size of the automorphism group of a graph

I am going through QUANTUM MECHANICAL ALGORITHMS FOR THE NONABELIAN HIDDEN SUBGROUP PROBLEM by Grigni et a. It is said on page 14 that the size of the automorphism group of a graph is either $1$ or ...
0
votes
1answer
20 views

which algorithm is used to find a leaf in a tree?

If we have a tree $T$=$G(V,E)$. What is the best algorithm used to find the leaf? Is it DFS: Depth First Search ?
0
votes
1answer
28 views

How to prove that Tree $T_1$ has a perfect elimination scheme (PES)

Give a tree graph $T_1$ =$(V,E)$ how can we prove that it has a Perfect Elimination Scheme :P.E.S P.E.S : is an ordering of the vertices, in such away that a vertex $v_i$ is simplical in the ...
0
votes
2answers
27 views

Adjacency Matrix of a Graph Length of Paths Proof

Let A be an adjacency matrix of a graph G. Prove that the (i, j)th entry of $A^2$ is the number of paths of length 2 between vertex i and vertex j. *I know the adjacency matrix will be a square ...
0
votes
0answers
9 views

Min-cut of a graph using node set partitions

Denote the $x-y$ min-cut value by $g(x,y)$, can I always find a partition of the node set $V$ into three non-overlapping sets $A, B, C$ each containing $x,y$ and $z$ respectively, such that a $x-y$, ...
1
vote
2answers
39 views

How do I solve this problem from graph theory?

Say I have a graph G with n nodes and m edges. Give each edge a capacity. If I am working in discrete time intervals (say days), how do I find the fastest way to move x amount of product from a source ...
1
vote
0answers
15 views

Graph with super nodes where each super node may have one or more sub-nodes in it

I have a question related to a problem I'm working on currently which is related to graph theory and complete sub-graph of size k (clique of size k). Let us say we have a graph where each node has one ...
0
votes
1answer
27 views

Topology of network from adjacency matrix : honeycomb?

In a percolative problem, I have noticed that all of the nodes of my system are connected to 3 other nodes. I started drawing a bit and realized that this could look like a honeycomb lattice. The ...
1
vote
0answers
14 views

eccentrcity of vertices in the given graph

I was calculating eccentrcity of vertices of the following generalized Petersen graph $P(15,2)$. For the vertx $u_0$, vertices $u_6$ and $u_7$ are farthest at a distance 4 and for the vertex $v_0$ ...
-2
votes
2answers
42 views

Im stuck on this question..is there a formula for this? [closed]

"Suppose G is a graph with 19 vertices and 154 edges. Show that G is connected."
0
votes
0answers
15 views

Induced subgraphs of a hypercube

Let $H_n$ be the graph whose vertices are $\{0,1\}^n$ with an edge between two vertices. If we are given a graph $G$, are there nice necessary and sufficient conditions for $G$ to be an induced ...
1
vote
2answers
29 views

Counting the Number of Faces on A Soccer Ball

I'm working on a problem in planar graphs, and I came across an interesting problem related to a graph of a soccer ball. Consider a soccer ball made entirely of hexagons and pentagons. Each "vertex" ...
2
votes
0answers
30 views

Kuratowski theorem methodology

Let's say I have a graph and I have to proof that is is not planar.If it is difficult to find a subgraph that is K3,3 or K5, how can I make the graph more clear so I can spot it.
0
votes
0answers
13 views

How to find the lowest cost of partition (A,B) in a complete graph

Given a complete graph $G=(V,E)$. The "intracost" of $A\subset V(G)$ is defined by the total weight of all edges with both ends in $A$. Given a complete graph $G=(V,E)$, where $|V(G)|=100$. Every ...
6
votes
1answer
79 views

$4$-regular graph with exactly one perfect matching

Can there be a $4$-regular graph with exactly one perfect matching? That is a graph that does have a perfect matching, but not two (not necessarily disjoint) perfect matchings.
0
votes
0answers
10 views

Why it is not possible to draw an interval graph with 4-Cycle without Chordal?

1- If want to draw an interval graph $IG$; I could not draw it of 4-Cycle without a chordal? WHY? 2- Is there any rules(cases) for which; when the graph is interval or not ?
0
votes
1answer
34 views

Given the number of edges in a connected graph, how does one solve for the number of vertices?

I know that given the number of vertices, the number of edges in a connected graph is $\frac{n(n-1)}{2}$. But how do we solve for the number of vertices, given the number of edges? I am stumped.
0
votes
1answer
15 views

What's the complexity class of Sub-Polytrees isomorphism?

In terms of Subgraph isomorphism I believe Directed Acyclic Graphs (DAG's) are in the np-complete complexity class. What about Poly-trees (oriented trees)? These are DAG's where the possible paths ...
2
votes
3answers
50 views

Finding the limit of ${n-1 \choose k}p^k(1-p)^{n-1-k}$ as $n$ goes to infinity

On this Wikipedia page on random graphs, they compute this limit to be $$\lim_{n\to\infty}\binom{n-1}kp^k(1-p)^{n-1-k}=\frac{(np)^ke^{-np}}{k!}$$ with $np$ constant. Any hints on how to get that? ...
0
votes
1answer
8 views

typical distance on lattice

Consider $V=\{1,\dotsc,k\}^d$ a $d$-dimensional lattice with $\{x,y\} \in E$ for $x,y \in V$ whenever $|x-y|_1=1$. Now we consider the typical distance, i.e. the distance of two uniformly at random ...
1
vote
0answers
22 views

Shortest path in divisors graph

There is a graph with $N$ vertices numbered from $1$ to $N$. Edge between $a$ and $b$ exists if and only if $a | b$ or $b|a$. If $a|b$ then the weight of the edge is $\frac{b}{a}$. If $b|a$ then the ...
0
votes
0answers
9 views

How to find the K-th thinnest paths in a graph

I'm looking for an algorithm to find the K-th thinnest paths in a directed graph (like Yen's algorithm for shortest paths). By "thinnest" I mean with the lowest weight per edge. For example, in this ...
0
votes
0answers
26 views

Can a Directed Acyclic Graph contain geometric information?

Can a Directed Acyclic Graph be sketched on top of a curved surface (and therefore contain geometric information)?
2
votes
1answer
18 views

Is the complement of interval graph an interval graph also?

In Graph Theory, IG is an interval graph, then the question is: Is the complement of IG also an interval graph? if so, then how can we prove it?
1
vote
0answers
33 views

Knowing number of nodes on a graph given depth and span

How can I know the maximum number of nodes in a graph, given that every node has degree K and that the graph has a diameter of at most ...
1
vote
1answer
13 views

Is there any real application of Max-Tolerance Graphs, Interval Graphs?

I have read one article about Max-Tolerance Graph:. Basically: Max-tolerance graphs can be regarded as generalized interval graphs, where two intervals $I_i$ and $I_j$ induce an edge in the ...
0
votes
0answers
53 views

Formulating shortest path (and tractable graphical model MAP) as submodular minimization

I'm trying to view maximum a posterior inference in discrete graphical model as a submodular minimization. For example, the linear chain model can be solved efficiently by the Baum-Welch algorithm. ...
1
vote
0answers
9 views

Reference requests on SP -graphs to outline its research areas

I want to understand SP graphs (series-parallel graphs) deeper for more elegant computation. I want to understand which area to research to understand sp-graph deeper: logical formalism? ...
1
vote
1answer
15 views

How many component has graph with 20 vertex at least 10 degree

How many maximum component can have a graph with 20 vertices and minimum 10 degrees? My proceeding: For first component I need one vertex with 10 degree and next 10 vertex. In sum 11 vertex. For ...
0
votes
1answer
21 views

Permutation Adjacency matrix

What is the name of a directed graph with a permutation matrix as its adjacency matrix? I mean if (N,E) is a graph and its adjacency matrix is a permutation matrix what is the suitable name for this ...
0
votes
1answer
45 views

What is a class of a graph?

I found this question on my textbook.What is the class of the graphs in which every Eulerian cycle is also a Hamiltonian cycle, but I don't understand what he means by class.
0
votes
1answer
33 views

Shortest path change in weighted graph

In a weighted graph does the shortest path between two vertices change if we add to all the weights the same positive number?
1
vote
1answer
30 views

Upper bound on chromatic number

Suppose I have a graph $G$ and a function $f:V(G) \to \mathbb{N}$ so that for all $v\in V(G)$ we have: $$| \{f(v)-f(w)\ge 0 \mid w \in N(v)\} | \le k.$$ Show that the chromatic number $\chi (G) \le ...
1
vote
2answers
39 views

Set Covering Problem for Weighted Graph

I am looking for solution of the following problem. Let $G$ be a weighted graph with (positive) weights. The length of a path in a weighted graph is the sum of the weights of the selected edges. The ...
0
votes
0answers
50 views

A good primer for Concrete Mathematics?

I've been watching MIT's Mathematics for Computer Science, from Fall 2010 whilst reading Concrete Mathematics. Honestly the topic seems like a hodgepodge of ideas. I can follow about 2/3 of the ...
0
votes
1answer
34 views

Graph models problem

10 children and 17 adults split into teams, say that they cooperated for a project with 2 children and 3 adults. Do they all tell the truth? Clarifying each adult i claims to have worked with three ...
0
votes
1answer
22 views

Is Bipartite Graph an Interval Graph if not, how can prove that?

Give a Graph $G(V,E)$ is a bipartite graph. How can we know if it is an Interval graph $IG$ or not? Is there any proof for : Bipartite Graph is not an Interval Graph #
1
vote
1answer
43 views

Can a simple undirected graph with 11 vertices and 53 edges have a Eulerian circuit?

I have gathered these but I can't connect them properly. The sum of the degrees of the vertices is 106. So d1+d2+d3+d4+d5+d6+d7+d8+d9+d10+d11=106 To have a eulerian circuit no vertex must have an odd ...
3
votes
1answer
52 views

Find Three Mutual Friends in a Mathematical Society

I am having trouble with the following combinatorics/graph theory problem: A mathematical society has three divisions (Pure, Applied, and Statistics), and exactly $n$ mathematicians in each ...
0
votes
1answer
21 views

Graph theory 2-connected graphs

So I have to prove that a 2-vertex-connected graph is also a 2-edge-connected graph, any ideas becuase I cant even start the proof.
3
votes
2answers
62 views

Show With High Probability, No Vertex Belongs to More than One Triangle

I am working on a random graphs problem, which is stated as follows: Suppose that $p = d/n$, where $d$ is constant. Prove that with high probability (w.h.p.), no vertex belongs to more than one ...
8
votes
1answer
114 views

How can the Hadwiger–Nelson problem depend on the axioms of set theory?

The wikipedia page on the Hadwiger Nelson problem says the following two things: The correct value may actually depend on the choice of axioms for set theory. and the problem is equivalent ...
1
vote
0answers
63 views

Weak, Regular, and Strong connectivity in directed graphs

There are 3 types of connectivity when talking about a directed graph $G$. 1) weakly connected - replacing all of $G$'s directed edges with undirected edges produces a connected (undirected) graph. ...
0
votes
1answer
33 views

Is there a graph that cannot be colored by k colors for k greater than its chromatic number? [closed]

Is there a graph that is not proper color-able using exactly k colors where k greater than the chromatic number (and smaller than number of vertices)?
2
votes
1answer
27 views

Simple Graph Degree Sequence Proof

Let G be a simple graph with degree sequence $(d_1,d_2,...,d_n)$. Prove that for each k, $0<k<n$: $$\sum_{i=1}^k d_i\le k(k-1)+\sum_{i=k+1}^n min(k,d_i)$$ I'm new to graph theory and proof ...
0
votes
1answer
52 views

How to know if two graphs are ismorphic or not?

For example in the picture above. I know that I need to calculate if both graphs have the same number of vertices and edges. But I don't know what I should do next to check if the graphs are ...
1
vote
2answers
59 views

The maximum number of girls you can accommodate in a row

I was playing around with the following problem: 'What is the maximum number of girls in a group of boys and girls that can be seated in a row of $x$ seats so that no $n$ girls are sat next to each ...