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

3
votes
1answer
54 views
+350

Vertex Reconstruction Conjecture For Asymmetric Graphs

Simple question: (a) Is it known whether all graphs G having trivial aut(G) are vertex reconstructible, and (b) what is the proof if it exists?
1
vote
1answer
28 views

What do you call a graph where the vertices are signed?

Let $G = (V, E)$ be a graph, and $f: V \to \{1,-1\}$ be a function assigning a sign to each vertex. What is this system $(G, f)$ called? In my current research, we've been using "oriented graph" ...
1
vote
1answer
26 views

Countability of the set of weighted graphs

Could you help me find the solution for this problem that consists in finding out wether the set of all weighted and finite graph is countable of not? As a reminder, a weighter graph can be seen as a ...
3
votes
1answer
36 views

Hopf algebra of graphs

Let $B$ be the set of isomorphism classes of finite graphs. Let $V$ be the $k$-vector space freely generated by $B$. I have heard that $V$ carries the structure of a Hopf algebra, and would like to ...
3
votes
0answers
32 views

Which graph with an automorphism group isomorphic to the quaternion group $Q_8$ minimizes $|V|+3|E|$?

In Symmetries of partial Latin squares, it is shown that for any graph $\Gamma=(V,E)$ with automorphism group $G$, there is a partial Latin square with $|V|+3|E|+49$ filled cells whose autotopism ...
0
votes
0answers
19 views

Displaying a graph with minimum overlapping edges

Context I am developing UI for a skill web for a mobile game. Each skill may have requirements from other skills, or sometimes no requirement at all. The problem The description above is ...
4
votes
1answer
37 views

Cubic Planar Graphs have $2^m-1$ Hamilton Cycles

I looked at the symmetric difference of hamilton cycle (HC) in cubic planar graphs and found that, together with the empty graph, they build a subgroup of the abelian group $\Omega$ of symmetric ...
1
vote
0answers
54 views

An extremal coloring problem

Is it true that there is $c\in\big[\frac{n}2,n+1\big]\cap\Bbb Z$ such that following holds if you assign single color to each edge of complete graph $K_n$: If $c$ colors are used in total, then ...
2
votes
1answer
31 views

Property of maximum matching

Let $G=(V,E)$ be a graph with no perfect matching. Then there exists a vertex v such that every incident edge is part of a maximum matching. I'm not sure how to prove this. How can every edge that ...
-1
votes
1answer
59 views

how many ziplines between two buildings? [closed]

There are two buildings facing each other, each 5 stories high. How many ways can Kevin string ziplines between the buildings so that: (a) each zipline starts and ends in the middle of a floor. (b) ...
2
votes
2answers
56 views

how can I proof that a graph with 2n vertices is bipartite

If I have a graph without triangels 2n vertices and n^2 edges is it a bipartite graph? I couldn't find a counter example.
2
votes
1answer
36 views

Planar graph and number of faces of certain degree

Let G be a 4 regular connected planar graph (with a planar embedding), where all faces are either degree 3 or degree 4. Then determine the number of faces of degree 3. Also, now suppose that every ...
2
votes
2answers
40 views

Size of a maximum matching of a complete multipartite graph?

Let $G=(V,E)$ be a complete multipartite graph on even number of vertices, with $V(G) = X_1\cup X_2\cup\ldots\cup X_k$, let $n_i := |X_i|$, and suppose $n_1\le n_2\le \ldots\le n_k$. The problem I am ...
1
vote
0answers
61 views

Graph Theory number of handshakes of couples

This is an Olympiad question which I now know the answer to, but I am a bit unsatisfied with it. So maybe someone can shed some light: Question: $5$ couples go to a party. Each person shakes the ...
2
votes
1answer
48 views

The Adjacency Matrix of Symmetric Differences of any Subset of Faces has an Eigenvalue of $2$…?

Assume a planar graph $G$ and let's call its faces $f_k\in F$. The adjacency matrix of any face $f_k$ has an eigenvalue of $2$, since it's a $2$-regular graph, i.e. a cycle. I want to show that the ...
0
votes
0answers
20 views

Probability of random walk visit in nonameanable graphs

Consider a vertex-transitive nonameanable graph. Consider a site $x$ having a graph distance $d$ from the origin and let $X(n)$ be a random walk starting from $x$. Is there a general upper bound as a ...
4
votes
2answers
61 views

Minimal edge cut

Suppose that $C$ is a minimal edge cut of a graph $G=(V,E)$ is it possible that the removal of $C$ can split $G$ into three components? I ask this because i'm reading a proof which states that it's ...
0
votes
1answer
41 views

how to define this directed graph satisfying these conditions?

I want to know the definition of a type of directed graph that satisfies these conditions: 1) this is a directed graph; 2) there is a directed spanning tree in this graph; 3) there is not any ...
0
votes
1answer
66 views

How many vertices for non-isomorphic graphs?

I started drawing planar, cubic, bipartite graphs consisting of faces with 4 or 6 Vertices only. I found that 6 4-faces are sufficient to do that. The smallest graph is a planar drawing of the cube. ...
1
vote
1answer
228 views

Connected, planar, 3-colorable graph with every face of degree 3 has an Eulerian circuit

I am trying to prove that: If G is a connected graph where every face has a degree of 3 and is 3 colourable then there exists and Euler tour. This is what I have done: For a graph to have an ...
0
votes
0answers
38 views

Graph Theory:Folkman Graph

I want to prove that Folkman graph is edge transitive but not vertex transitive, and I don't know how can I start to prove, any help would be great thanks.
2
votes
0answers
28 views

An evenly divided $k$ coloring of an $(n,d,\lambda)$ graph leaves one vertex adjacent to all $k$ colors, given $k\lambda \leq d$.

(This is problem 9.2 from Alon and Spencer's The Probabilistic Method) Let $G = (V,E)$ be an $(n,d,\lambda)$-graph, suppose $n$ is divisible by $k$, and let $C:V \to \{1,2,\ldots,k\}$ be a ...
0
votes
0answers
14 views

Graph embeddings for informational networks

Say we have a fabric of computers (or anything that communicates) all talking to each other in the structure of a graph. If we have a lot of them, we can treat this graph as an approximation to a ...
0
votes
1answer
45 views

Diameter of random graph.

Basically I was given a random graph with fixed probability and I need to prove that the diameter of the random graph is asymptotically 2. See the following picture for the detail of the question. ...
3
votes
1answer
37 views

A problem on counting sub-graphs

How many distinct sub-graphs of a complete graph of $n$ labelled vertices are there, such that the sub-graph is a spanning tree connecting all the vertices and the degree of no vertex is more than ...
2
votes
0answers
68 views

Are triangles rigid in 4 dimensions?

I have read in a couple of sources that a graph with n vertices is rigid in d dimensions if and only if its rigidity matroid has rank nd - d(d+1)/2. C3 (a triangle graph) has a rigidity matroid of ...
0
votes
0answers
53 views

What is a nontrivial graph?

I've been operating happily under the definition that a nontrivial graph is a graph with at least two vertices for some time. Today I came upon a source which defined a nontrivial graph as a graph ...
0
votes
0answers
18 views

how to partition the number of vertices of a given graph into certain subset?

I am curious about this question in graph theory. Given an integer $d$, how to find the minimum partition the vertex set of a given graph $G$ into a few subsets, such that any two vertices in the ...
0
votes
0answers
24 views

Reference request: maximize the total weight along the path on the graph.

I am looking for the reference(s) where the following computational problem is discussed: Given a weighted graph $G$ where each vertex $v_i$ has some weight $w_i$ and a number of "vertices visited" ...
1
vote
2answers
66 views

Number of cycles in complete graph

How many number of cycles are there in a complete graph? Is there any relation to Symmetric group?
3
votes
2answers
79 views

Graph theory-related problem, unit distance graph, pairs of people with restraining orders

This problem is for my own exploration, not for class. The problem goes as follows: There are $n$ pairs of people with restraining orders against one another. However, all $2n$ people are friends ...
1
vote
1answer
48 views

bound on vertices of graph with path

Question: Let $G=(V,E)$ be a graph with $n$ vertices that has vertices $u,v$ such that $dist(u,v)=3b$ for a positive integer $b$. Let $\delta$ be the minimum degree of $G$. Prove that ...
0
votes
1answer
60 views

Appropriate Graph Theory Concepts

I am working in a different domain and I have very basic information about the graph theory concepts. Trying to map my problem into graph theory and looking for the concepts and algorithms applicable ...
0
votes
0answers
57 views

Are there exact methods to solve the Path cover in bipartite graphs?

We consider a simple graph $G =(V; E)$. The well known Path Cover problem is NP-complete on all graph classes on which the Hamiltonian path problem is NP-complete, including planar graphs, bipartite ...
2
votes
2answers
29 views

Statistical independence of degree in Erdos-Renyi random graph model

Let $d(v)$ denote the degree of the vertex $v$ in the random graph $G$ coming from the Erdos-Renyi model. I would like to calculate $\mathbb{E}[d(v) d(u)]$. Clearly, $$\mathbb{E}[d(u)] = ...
4
votes
1answer
80 views

Brain teaser solution in Graph Theory / Ramsey Theory

I have a solution to the following brainteaser, which I think is the correct answer, but I haven't been able to come up with a way to prove that it's the right answer. I know very little about graph ...
0
votes
0answers
25 views

In bipartite directed graph, how to efficiently find nontrivial edge values such that for each node, sum of edge values is zero?

Suppose I have a set of sources U and a set of sinks V and a set of directed edges E going from elements of U to elements of V. I want to find a vector z of size |E| (each value of z is assigned to ...
0
votes
1answer
43 views

Shaking-Hand problem

We consider a relation : " a person X shakes hand with Y" . Obviously if X shakes hand with Y , then Y shakes hand with X . In a gathering of 99 persons, one of following statements is always true, ...
0
votes
1answer
21 views

What is the correct statement of this “theorem” about 2-factorability of graphs?

According to Wikipedia: If a graph is $2$-factorable, then it has to be $2k$-regular for some integer $k$. This can't be right: Question. What's the correct statement of this "theorem" ...
0
votes
0answers
19 views

Graph Theory Help, Assortativity Coefficient with Weighted Edges. Remaining weights vs. Total weights. (undirected graph)

a combo network analysis and igraph/r question. It is cross posted with stackoverflow (and I will hopefully not be laughed away). I am trying to find the assortativity coefficient for an undirected ...
0
votes
2answers
33 views

Orientation of Edges on Graphs with Vertex Degree Constraints

Suppose I have a graph $ G = (V,E) $ such that each vertex $ v \in V $ has degree 4. Can I always choose an orientation of edges (ie. arrows drawn on edges) such that each vertex has two incoming ...
1
vote
2answers
49 views

Number of finite-state machines with $n$ states, output alphabet size $a$, and binary input

How many FSMs are there where the machine has $n$ states, reads a binary symbol at each time-step, and may or may not output a symbol from an alphabet of size $a$ after each transition?
1
vote
1answer
26 views

Shortest path in a hypercube graph

A* algorithm is one of the algorithm which produces a shortest path in a given graph. I am interested in knowing, is there any property of d-dimensional hypercube which allows the parallel computing ...
4
votes
1answer
62 views

Minimum 6-connected graph on 200 vertices

Find the samllest number of edges in 6-vertex-connected graph on 200 vertices. I think that the answer is 600 , using the fact that $\delta(G) \geq \kappa(G)$. But the smallest ...
0
votes
2answers
43 views

Good reference material for graph theory [duplicate]

Could anyone please suggest either a book or some reference material either online or as printed material for graph theory?
3
votes
1answer
46 views

Expected number of return for a random walk on a graph

Let $G$ be a simple, connected undirected graph of order $n$ and vertex set $\{v_1,\ldots,v_n\}$ and let $P = (p_{i,j})$ be a $n \times n$ matrix where $$p_{i,j} = \left\{ \begin{array}{ll} ...
0
votes
1answer
55 views

Do cycle graphs determine groups up to isomorphism?

This erroneous version of the wikipedia article for Cycle Graphs stated that the cycle graph of different groups could be the same. The immediate error is that it stated that the cycle graph of ...
0
votes
1answer
19 views

How does one prove that the automorphism for a cycle with more than two vertices is equivalent to dihedral group?

I'm trying to prove that the automorphism group of a cycle $C_n$ with $n \ge 2$ is $D_n$, the dihedral group. It's easy to prove all of the members of $D_n$ are automorphisms of $C_n$. But I'm stuck ...
2
votes
1answer
68 views

Knapsack in graph

This question is from job interview for a software company.   "You are given an undirected connected weighted graph with $n$ nodes. The weight function represents transportation costs. In ...
1
vote
1answer
53 views

Graph where every vertex has degree 3, perfect matching?

Suppose $G$ is a graph where every vertex has degree $3$. There is no single edge which separates the graph. My question is, must $G$ necessarily have a perfect matching? I tried drawing some graphs ...