Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, ...

learn more… | top users | synonyms

1
vote
4answers
229 views

Counting simple 4-cycles in an undirected graph [closed]

I'm looking for an algorithm which just counts the number of simple and distinct 4-cycles in an undirected graph labelled with integer keys. I don't need it to be optimal because I only have to use it ...
-2
votes
1answer
222 views

the number of connected components [closed]

I am finding a solution of the following problem. I would like you to give a short proof. Let A be the adjacency matrix of a d-regular graph G. Prove that d is an eigenvalue of A with multiplicity at ...
1
vote
1answer
126 views

Upper-bound for maximal-cliques on perfect graphs

It has been proved by Moon and Moser in 1965 that any finite simple graph has at most $3^{|V|/3}$ maximal cliques. Still, some hereditary classes of graphs have very few maximal cliques in comparison ...
4
votes
1answer
123 views

Epidemic threshold

Need some help / ideas to proceed. Stuck for a while on this. In the literature of epidemic theory, it is found that the epidemic threshold is $1/\lambda_{max}(A)$ where $\lambda_{max}(A)$ is the ...
3
votes
1answer
119 views

Have chordal outerplanar graphs been studied before?

Recall a graph is chordal if it contains no induced cycle of length 4 or more, and outerplanar if it has a crossing-free embedding in the plane such that all vertices are on the same face. While ...
0
votes
0answers
89 views

Articles on (Strongly Regular) Graphs and Covering Arrays / Covering Designs?

In their book "Algebraic Graph Theory" Godsil and Royle mention the connection of strongly regular graphs with latin squares and thus Orthogonal Arrays (Chapter 10.4). There seems not to be much ...
6
votes
1answer
144 views

A family of skew-symmetric matrices corresponding to cycles in graphs

When investigating loops in Markov chains I ran into the following observation. A cycle in a graph $G$ with $n$ vertices may be represented by a matrix $\Gamma \in \mathbb R^{n \times n}$ having the ...
0
votes
0answers
65 views

Existence of a sequence of (almost) Moore irregular graphs embedded on closed surfaces

Let $S_{g}$ denote the genus $g$ closed orientable surface. I'm interested in disproving the existence of a certain configuration of simple closed curves on $S_{g}$. I'd be happy to go into more ...
8
votes
3answers
295 views

Characteristic polynomials of trees and E8

In thinking about constructing manifolds via surgery or plumbing, the following combinatorial problem comes up: If T is a tree with adjacency matrix A and I is the identity matrix of the same order, ...
3
votes
1answer
192 views

Equivalence of Hadamard Graph and Hadamard Matrix

I'm reading Distance Regular Graphs by Brouwer, Cohen, and Neumaier. In section 1.8, they explained Hadamard graphs. Conversion from a Hadamard Matrix into a Hadamard Graph An $n$-Hadamard graph $G$ ...
5
votes
2answers
155 views

Reflexive (hyperbolic) graphs

Is there an effective description of the graphs such that exactly one eigenvalue (of the conventional adjacency matrix) is $>2$ whereas all others are $\le2$? By "effective" I mean something ...
0
votes
0answers
59 views

Lemma about complete subgraphs of r-parite graphs by Bollobás

Lemma connected with counting z(m,n;s,t): Let $m, \, n,\, s, \, t, \, r, \, k$ be integers, $0 \leqslant s \leqslant m$, $0\leqslant t \leqslant n$,\ $0\leqslant k$, $ 0\leqslant r \leqslant m$ and ...
3
votes
2answers
307 views

spectrum of an adjacency matrix

The adjacency matrix of a non-oriented connected graph is symmetric, hence its spectrum is real. If the graph is bipartite, then the spectrum of its adjacency matrix is symmetric about 0. A few ...
5
votes
2answers
217 views

Universal graphs on higher cardinals

The Rado graph contains every finite graph as induced subgraph, and its also holds for countable graphs. So it is an universal graph of size $\aleph_0$, which contains all graphs of size $\aleph_0$ as ...
1
vote
1answer
175 views

Counting edges in embeddable CW-complexes in R^3

Using Euler's formula ($V-E+F = 2$ where $V$, $E$ and $F$ are the number of vertices, edges and faces), we can easily count the number of edges in maximal graphs that are embeddable in plane: 3n-6. I ...
15
votes
0answers
219 views

Is the Poset of Graphs Automorphism-free?

For $n\geq 5$, let $\mathcal {P}_n$ be the set of all isomorphism classes of graphs with n vertices. Give this set the poset structure given by $G \le H$ if and only if $G$ is a subgraph of $H$. ...
3
votes
0answers
73 views

What is this expander-mixing-type graph property?

Fix $C>0$. I am interested in graphs with the following mixing property: $$\Big|E(S,T)-\frac{1}{2}|S||T|\Big|\leq C\sqrt{|S||T|\max\{|S|,|T|\}}$$ for every disjoint $S,T\subseteq V$. Note that ...
2
votes
1answer
150 views

Regular graphs with $a$ and $b$ Hamiltonian edges

Special case of this question. Let $G$ be $r$-regular Hamiltonian graph. An $a$ edge is an edge which is on every Hamiltonian cycle. A $b$ edge is an edge which is on no Hamiltonian cycle. $a(G)$ ...
5
votes
6answers
408 views

Random planar, bipartite graphs

I have a need to generate random planar graphs none of which have an odd cycle, i.e., bipartite graphs. I know there is a substantial two-decade literature on random planar graphs, little with which I ...
2
votes
1answer
94 views

Subdividing toward a unit distance graph in the plane

I just want to ask, what is the significance of subdividing a graph toward a unit distance graph? I have seen several studies of it but I cannot find what its importance. I mean, like the study of ...
5
votes
1answer
276 views

Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$. Consider the bipartite ...
7
votes
2answers
331 views

Graphs with many edges avoided by Hamiltonian cycles

Let $G$ be a $3$-connected Hamiltonian graph with at least one edge that belongs to each H-cycle of $G$. Some authors (e.g. in the link given here) call such an edge an a-edge and an edge that belongs ...
5
votes
2answers
200 views

Number of unlabelled planar graphs

What are the best known bounds on the number of non-isomorphic (unlabelled) planar graphs on $n$ vertices? Is there a simple proof that this number is at most exponential in $n$?
1
vote
1answer
143 views

Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity

While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is $NP$-complete while the complexity of ...
6
votes
0answers
284 views

the length of paths in a specific graph

Let $n$ be a positive integer and $K$ be the set of all the $2$-elements subsets of $\{1,2,...,n\}$,then $|K|= \binom{n}{2}$. Define $$S=\{P\subseteq K:\bigcup_{I\in P}I=\{1,2,...,n\}\}.$$ For any ...
1
vote
1answer
200 views

Is this Graph parameter known?

Let $\lambda(G)$ denote the edge-connectivity of $G$. Consider the following parameter: $\rho(G) = \max_{X \subset V(G)} \min(\lambda(G[X]), \lambda(G[V(G) - X]))$ Has this parameter been studied? ...
4
votes
1answer
107 views

Graph Verification Problem

Does anyone know whether the following problem has been solved or has an easy solution? Given a graph $(V,E)$, two subsets of the vertices $U_1=\{u_1, \dots, u_r \}, U_2=\{v_1, \dots, v_s \} \subset ...
2
votes
0answers
50 views

Minimal set of 2-2 Pachner move null sequences on a (nonplanar) trivalent graph?

A "null sequence" is of course a sequence of Pachner moves (inside a closed area) that doesn't change the trivalent graph. E.g. doing the same Pachner move twice (leads to orthogonality of 6j symbols) ...
5
votes
0answers
112 views

Complexity of finding three perfect matchings with no edge in common in a bridgeless cubic graph

According to a conjecture: Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common. Equivalent statement here Main question: ...
13
votes
3answers
640 views

Are infinite planar graphs still 4-colorable?

Imagine you have a finite number of "sites" $S$ in the positive quadrant of the integer lattice $\mathbb{Z}^2$, and from each site $s \in S$, one connects $s$ to every lattice point to which it has a ...
2
votes
1answer
149 views

About an equivalent to Tutte's 5-flow Conjecture

A while back I remember reading that F. Jaeger proved that Tutte's $5$-flow conjecture is equivalent to a statement about the co-planarity of a certain set of points in some euclidean space. But I ...
3
votes
2answers
279 views

Which directed graphs have a normal adjacency matrix?

I am working on a problem in matrix analysis and I am looking for certain types of normal matrices. I suspect that these "special" normal matrices arise as adjacency matrices of certain graphs. My ...
3
votes
2answers
230 views

Can the Vertices of cubic graph be partitioned into and induced cycle and a forest?

Let $G$ be a $2$-connected $3$-regular graph. Can $V(G)$ be partitioned into $V_1$ and $V_2$ where $G[V_1]$(the induced subgraph on $V_1$) is a cycle of $G$ and $G[V_2]$ is a forest (Acyclic ...
2
votes
1answer
139 views

Is the set of edge of a cubic graph the union of a cycle and and an Acyclic graph?

Let $G$ be a $2$-connected $3$-regular graph. Is it true that $E(G) = E_1 \cup E_2$ where $G[E_1]$(the induced subgraph on $E_1$) is a cycle of $G$ and $G[E_2]$ is a forest (Acyclic subgraph) of $G$? ...
2
votes
0answers
81 views

Counting regular Hypergraphs

The problem of counting regular graphs on $n$ vertices is notoriously hard. It seems like counting regular hypergraphs on $n$ vertices should be much easier (I am placing no uniformity condition). ...
0
votes
1answer
81 views

Topological Irreducible graphs for the projective plane

I learned that there are 103 topological irreducible graphs for the projective plane but I am unable to find examples of said graphs. I am unsure of how to find them on my own and I would like to see ...
4
votes
1answer
121 views

Counting the number of $(d_v,d_c)$ regular bipartite graphs

I am trying to count the number of $(d_v,d_c)$ regular bipartite graphs. To be specific, let $n,m,d_v,d_c$ be positive integers such that $$n\times d_v=m\times d_c.$$ Then, what is the number of ...
2
votes
1answer
181 views

Coloring of subgraphs of G^n

Let $G=(L,R,E)$ be a finite bipartite graph, such that for each $v\in L\cup R: deg(v)>0$. Define $E^{(n)}=\{(\overline{l},\overline{r}) | \overline{l}=(l_1,...,l_n)\in L^n , ...
3
votes
1answer
212 views

Expected Value for a Connected Graph

Consider a connected graph of N nodes. Assign randomly to each node a distinct number from 1 to N. For each node consider the maximum adjacent value or itself if all adjacent values are smaller. ...
1
vote
0answers
132 views

A connection between nonplanar complete graphs and the alternating group?

I didn't get any response on MSE so I though I'd give this a try here (my question on MSE). I went to an undergrad's senior honors thesis presentation a while ago. She was discussing crossing numbers ...
2
votes
1answer
180 views

Graph of Grassmannian

Let p be an integer, and let G be the graph $(V=Gr(k,\mathbb{F}_q ^n),E)$ where: $Gr(k,\mathbb{F}_q ^n)$ is the set of all subspace of $\mathbb{F}_q$ of dimension k, and $E=\{ W_1,W_2 \in V | ...
5
votes
1answer
274 views

A new question about maximal independent sets in regular graphs

This is a question inspired by "A question about independent set in regular graphs". Suppose that $G$ is a simple $r$-regular graph with $n$ vertices. We say $H$ is a dominating set for $T$, if for ...
11
votes
2answers
381 views

Strongly connected directed graphs with large directed diameter and small undirected diameter?

This question is an attempt to make progress on domotorp's interesting challenge. This question was originally asked in two parts; the former of which was answered by Ilya Bogdanov, and the latter of ...
6
votes
0answers
138 views

Uniformly sampling from the set of all simplicial maps

Let $K$ and $L$ be finite simplicial complexes that remain fixed throughout. How does one efficiently sample (according to the uniform distribution) elements from the finite set of simplicial ...
0
votes
1answer
78 views

Basis of Cycle Subspace of a Graph

Let $G$ be a $2$-connected graph and for $e \in E(G)$ denote by $\mathcal{C_e}$ the set of all cycles(circuits) of $G$ containing the edge $e$. For what set of edges does $\mathcal{C_e}$ contain a ...
-1
votes
2answers
155 views

spanning tree of a graph of minimum degree three

Does each graph of minimum degree three admit a spanning tree whose vertices have degree three (exactly) except the leaves (degree one)?
3
votes
1answer
161 views

Minimum distance between Hamiltonian cycles in cubic Hamiltonian graph

It is $NP$-hard to find constant factor approximation of longest cycle in cubic Hamiltonian graphs. Therefore, finding a Hamiltonian cycle in a cubic Hamiltonian graph is NP-hard. By Smith's theorem, ...
0
votes
1answer
248 views

A question about independent set in regular graphs

Suppose that $G$ is a simple $r$-regular graph with $n$ vertices. We say $H$ is a dominating set for $T$, if for every vertex $v\in T$, we have $v\in H$ or there is a vertex $u\in H$ such that $vu\in ...
4
votes
1answer
247 views

Fundamental Cycles of a graphs

For a $2$-edge-connected simple graph $G$ and a tree $T$ of $G$, let $C_e$ be the unique cycle in $T + e$, $e \in E(G) - E(T)$. Define the set $\mathcal{C}(T) = \{C_e | e \in E(G) - E(T)\}$. Now ...
1
vote
0answers
140 views

Can assigment of Cayley graphs be functorial?

Let $G$ and $G'$ be finitely generated groups and $f:G\to G'$ a homomorphism. First question: for a given $f:G\to G'$ it possible to select generating sets $S\in G, S'\in G'$ so that their would be a ...