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
2answers
67 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
72 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
109 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
95 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
101 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
99 views

Automorphism groups of self-complementary graphs

Does every self-complementary graph has a non-trivial automorphism group?
0
votes
1answer
107 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
136 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 ...
1
vote
1answer
201 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
116 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
104 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
37 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
150 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
122 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
54 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
165 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
51 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
52 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
218 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
119 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
1k 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
46 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
160 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
92 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 ...
5
votes
3answers
10k 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 ...
2
votes
1answer
55 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
64 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
183 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
68 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
109 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
253 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
74 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
76 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
603 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
71 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
75 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
33 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
519 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
198 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
90 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
158 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
31 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
70 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
763 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 ...
2
votes
1answer
135 views

Finding the shortest/“most negative” closed directed trail in a weighted digraph with negative weights

I'm using the following definition of a "closed directed trail": a closed directed trail is a directed cycle in a digraph where all edges are distinct. Note that vertices may be repeated, so long as ...
0
votes
2answers
87 views

The strange case about the outer face…

Let $f_k$ denote the face degree of a cubic planar graph, then from Euler's Formula it follows that: $$ \sum_{k=1}^F f_k = 6F-12 \tag{1} $$ Now I tried to construct some graphs from that, so let $F=4$ ...
3
votes
1answer
103 views

Increasing the chromatic number of a graph?

The classic join of two graphs $G$ and $H$ results in $G \vee H$ whose chromatic number $\chi(G \vee H)$ = $\chi(G)$ + $\chi(H)$. $G \vee H$ = $G \cup H \cup$ Complete bipartite between vertices of ...
1
vote
0answers
86 views

A basic intuitive question on basis

From Zorn's lemma, basis can be thought of as a maximal independent set as well as minimum cover (covering all the vectors). Is this observation correct ? Can this observation be related to the usual ...
1
vote
1answer
220 views

How is percolation defined and measured in social networks?

From the wikipedia article on percolation it appears that the theory is applicable to graphs in general, and this presentation describes the theory nicely. This review article on complex networks ...