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

2
votes
1answer
150 views

Square of the expectation of number of edges not in a triangle in random graph

The following question is from page 27 in the book Graphical Evolution, An introduction to Theory of Random Graphs by Edgar M. Palmer. I feel that my argument is correct (who doesn't?), but the answer ...
3
votes
2answers
190 views

Efficiently identifying spam honeypots

I realise that the title is computing specific, but I think the underlying problem is general - I just don't know how to phrase it more generally (which may be part of my problem). So I am asking ...
5
votes
1answer
162 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 ...
3
votes
2answers
175 views

Is there any way to count cycles of given size by that graph's spectrum?

Is there any way to count cycles of given size by that graph's spectrum? for example for $k=3$ the number of triangles in $G$ is $1/6\cdot\sum_{\lambda \in \mathrm{Spectrum}(G)} \lambda^3$ is there a ...
0
votes
1answer
57 views

Troubles solving a graph problem

I'm having troubles finding a solution to this problem. Having these datas, I'm supposed to prove that a 1 graph is possible. Here, $\Gamma^+(W)$ is the outdegree and $\Gamma^-(W)$ is the indegree of ...
3
votes
2answers
74 views

Constructing graphs without cycles of length <= 4

I need undirected graphs without triangles and squares with as many edges as possible. It seems the number of edges is under $n \sqrt{n}$, but how to construct a graph?
7
votes
0answers
74 views

Special subgroup of a group of order $n$ [duplicate]

I apologize if this seems elementary but I don't know how to deal with. Let $G$ be a group of order $n$ and let $ \emptyset \ne S \subseteq G$. Is it true that $S^n :=\lbrace s_1\cdots s_n \; | \; ...
1
vote
1answer
195 views

cluster validation and determining number of clusters

I want to find number of cluster in the real world data set. So, I validate the spectral clustering by using some indexes as shown in figures below? But as you seen in figures the results are very ...
1
vote
1answer
114 views

¿Mathematical induction GRE math?

Im studing for the GRE math subject test...i can´t get the followin problem: Using Mathematical Induction, show that it is possible to color with only two colors the regions formed by n lines in the ...
0
votes
1answer
135 views

Determine all possible automorphisms of a graph

Let $G$ be the undirected graph whose vertex set is $\{a,b,c,d,e\}$ and edge set $\{ab, ae, bc, be, cd, ce, de\}$. The graph is drawn below: Let $V$ denote the set of vertices of the graph G ...
3
votes
1answer
112 views

Automorphism groups of self-complementary graphs

Does every self-complementary graph has a non-trivial automorphism group?
0
votes
1answer
113 views

Flip graph of point set [closed]

Is the flip graph of every point set in $\mathbb R^3$ connected? If not, is there a set with an isolated node? Def: For a point set $S$, the flip graph of $S$ is a graph whose nodes are the set of ...
2
votes
1answer
178 views

Number of graphs with vertices of only even degree. [duplicate]

This is an exercise I don't know how to solve, as I am preparing for an exam it would be great if you could help me with it. Show that for $n > 0$ a number of graphs with vertices from set ...
2
votes
1answer
345 views

Graph (or Group) in Astronomy

Is there an application of graph theory (or group theory) in astronomy. If there is, refer me some references.
5
votes
2answers
166 views

Compactness theorem, directed graph

We study a language L and the axioms of directed graphs. A directed graph is connected if there's for every 2 points a finite path. Prove that ther's no theory T such that it contains the axioms of a ...
0
votes
1answer
159 views

How many friends of friends of friends?

I'm trying to determine how many second degree (friends of friends), and third degree (friends of friends of friends) a typical individual has based on the current number of friends he or she ...
0
votes
1answer
38 views

Edge coloring question

I need your help / advice for the next question: Let $G = (V;E)$ be a 4-regular plane graph with $E = X \cup Y$ (disjoint union). For the following conditioning: For each vertex , its four ...
0
votes
0answers
188 views

Variance of the first return time of a simple random walk on an hypercube graph

I am trying to solve this problem.... I have a simple random walk on a $d$-cube (finite graph). At each vertex of the graph, the particle chooses one of $d$ edges equally likely. I need to calculate ...
4
votes
2answers
143 views

Some equivalence relation from flipping binary trees

I know almost nothing in combinatorics, so this question might be very easy, or well-known. Fix a number $n$. We will consider rooted planar binary trees with $n$ leaves. We will distinguish between ...
2
votes
1answer
61 views

Complete Graph Invariant

A graph invariant $I(G)$ is called complete if the identity of the invariants $I(G)$ and $I(H)$ implies the isomorphism of the graphs $G$ and $H$. Is there any example for complete graph invariant?
0
votes
1answer
215 views

number of digraphs where each indegree and outdegree equals 2

up to isomorphism, how many unlabeled digraphs with 5 nodes have each indegree=2 and each outdegree=2? for 3 nodes, the answer is 1 (each node points at every other node, a 3-cycle of double arrows). ...
0
votes
0answers
52 views

a doubt over a term in paper of graph theory

I was reading a paper http://www.sciencedirect.com/science/article/pii/S0166218X08001960. On the page 38, under the topic The vertex hierarchy I have doubt. From where did the following term come? ...
2
votes
2answers
56 views

Connected cubic $s$-regular graph

Let $X$ be connected cubic $s$-regular graph then $|Aut(X)| = 2^{s-1}\cdot 3\cdot |V(X)|$. I want a reference for proof.
3
votes
1answer
265 views

In every bipartite graph G, there exists a vertex v such that v is matched in every maximum matching

As a part of König's Theorem proof I have to prove following lemma: In every bipartite graph G, there exists a vertex v such that v is matched in every maximum matching. Any help?
1
vote
1answer
150 views

What does small eigenvalue gap imply for a graph?

Knowing a graph has good expansion has well-known implications. What can we say about graphs with $1-\lambda = O(\log n/n)$, where $1-\lambda$ is the difference between the two largest eigenvalues of ...
3
votes
1answer
3k views

Subgraphs of Complete graphs

I have been studying a little graph theory on my own and a simple google search has not helped so I am deciding to turn to math stack exchange. My question is: Given a complete graph $K_{n}$ where ...
1
vote
1answer
47 views

Finding path, the sum of whose numbered edges is 48

Let $G$ be a graph with vertices $\{1,\dots,10\}$. Two vertices $a,b$ have an edge if $a\mid b$ or $b\mid a$. Find a path in $G$ so that the sum of the corners in the path equals 48. I solved ...
2
votes
1answer
199 views

Counting Components via Spectra of Adjacency Matrices

I trying to implement a test for $k$-connectedness of cubic triangle-free graphs $G$ given their adjacency matrix $A$. My idea is the following: For $1$-connectedness, we construct a new graph $G'$ ...
4
votes
1answer
111 views

Bipartite subgraph having minimum degree

Prove that every graph $G$ with minimum degree $2m$ will have a bipartite subgraph having minimum degree $m$. I have tried this proof by first taking one vertex $v$ and consider it in set $D_0$. Then ...
8
votes
4answers
19k views

Prove two graphs are isomorphic

I have identified two ways of showing it isomorphic but since it is a 9 mark question I dont think i have enough and neither has our teacher explained or given us enough notes on how it can be ...
3
votes
1answer
72 views

Construction of regular graphs

What are the ways to create regular graphs using any number of vertices, under the below rule for adjacency between vertices. Rule: Vertex A is adjacent to vertex B if and only if vertex B is within ...
2
votes
1answer
41 views

doubt about my last question

I have a very basic doubt. If we talk about rooted graph, can we consider any graph whose one vertex is labeled in a special way to distinguished it from other vertices or only rooted tree. this doubt ...
0
votes
1answer
69 views

tough inequality for a graph theory problem

I am stuck at a step in a graph theory problem. I have to prove that $$ \frac{d\cdot(d-1)^k}{(d-2)} \leq d^k$$ for $d,k \geq 3$. Here $d$ actually refers to degree of a graph and $k$ the radius. The ...
0
votes
3answers
242 views

Is this the only planar cubic graph with six squares and two hexagons?

Is this the only planar cubic graph with six squares (five inside, one outside) and two hexagons? How to prove that? Allowing for multiple edges I can find another, but without not...
0
votes
1answer
70 views

$R\subset S\times S$ for $S=\{1,2,3\}$: A Graph-Theoretic Approach

So I am given the relation $R=\{(1,1),(2,2),(3,3),(1,2),(1,3)\}$ and asked which of the properties reflexive, symmetric, or transitive are held in the relation, but what I am thinking is that this can ...
2
votes
1answer
171 views

Draw a cubic planar graph with six faces of degree $4$ and one with $6$…

I'm currently playing around with Euler's Formula and found the following for cubic planar graphs: $$ \sum_{k=1}^F f_k = 6F-12, $$ where $f_k$ is the degree of the $k$th face. I tried to apply this ...
0
votes
2answers
351 views

Does a graph contain a 3-cycle or a 4-cycle

Given a graph $\mathscr G$, that has 100 nodes each with a degree can you show that this graph contains a 3-cycle and/or a 4-cycle? The graph in question represents 100 people at an event, and they ...
0
votes
0answers
78 views

Lifting automorphism problem - classical approach

Let X, Y be connected graph and Y be a covering graph of X and A be asubgroup of Aut(X). let B be lift of A. we know there is a group epimorphism from B to A. What is this epimorphism?
2
votes
0answers
88 views

How can I understand the Hadwiger conjecture?

I would like to understand the Hadwiger conjecture and I would like to read books that will allow me to both understand it and also get a grasp of the theory it is related to. Regards
12
votes
2answers
1k views

Determining the number of valid TicTacToe board states in terms of board dimension

I am attempting to find a closed form equation in terms of $n$, for the number of valid Tic-Tac-Toe board states (ignoring symmetry), where the board has dimension $n \times n ,\; 0 \lt n,\;n \in \Bbb ...
0
votes
0answers
86 views

Is there a special name for planar graphs, when the outer face has the highest degree?

Is there a special name for planar graphs, when the outer face has the highest degree? $\hskip1.3in$ Like $a)$, where $f_{\text{outer}}=6$; not like $b)$, where $f_{\text{outer}}=4$...
5
votes
1answer
83 views

Origin of the term “planar graph”

I would like to know who coined the term planar graph? I was able to trace the term back to a paper "Non-Separable and Planar Graphs" by Hassler Whitney, Proc. Natl. Acad. Sci USA. 1931 February; ...
1
vote
0answers
38 views

Embeddings and Covering faces?

I have a dude with the following problem. Suppose you have an 2-cell embedding of some simple graph $G$ on a orientable type surface $S_g$ (for example a plane graph), and you desire to find a set $A ...
1
vote
1answer
685 views

Graph Theory Question involving: Nodes, edges, degrees and paths

a) For the graph (in link above), write out the set of nodes, the set of edges, and the degree of each node. [6 marks] I have attempted this question, however wanting to find out if it is correct ...
1
vote
2answers
244 views

How well can we embed graphs with shortest path metric into $\mathbb{R}^2$ with Euclidean metric?

If we take the integer lattice in $\mathbb{R}^2$ and make edges from $(m,n)$ to $(m+1,n)$ and $(m,n+1)$, you get your typical city block street layout, and if we put the shortest path metric on the ...
1
vote
0answers
92 views

A question on graphs

Do there exist a family of graphs with $\Omega(N_{G}^{c})$ edges for some fixed $c > 0$ with the property: $$\left|\alpha\left({G \boxtimes \bar{G}}\right) - \alpha\left({\overline{G \boxtimes ...
0
votes
1answer
294 views

Algorithm of creating dual graph from a plannar graph

Depite i have some ideas to create a dual graph from a planar graph, but i prefered to ask it here. Is there any algorithm for this purpose? Thank you so much.
1
vote
0answers
36 views

Graph class of a “polygon tree”

A cycle is a polygon tree. A new polygon tree $G′$ can be created out of an existing polygon tree $G$ by adding a cycle which shares exactly one edge with graph $G$. I want to know which graph class ...
2
votes
1answer
71 views

Are these two proofs regarding coloring valid and complete?

Question #1) Prove or disprove: If G is a graph and for every vertex $v \in V(G), \chi (G-v) < \chi (G)$, then for every subgraph H such that $H \neq G, \chi(H) < \chi(G)$. Question #2) Prove ...
11
votes
3answers
1k views

How many non-isomorphic ways a convex polygon with $n + 2$ sides can be cut into triangles?

From Wikipedia: The Catalan number $C_n$ is the number of different ways a convex polygon with $n + 2$ sides can be cut into triangles by connecting vertices with straight lines (a form of Polygon ...