The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
0answers
22 views

When are the cardinalities of 2-factors in a graph equal?

Given a graph $G$, if we can partition the edges into pairwise disjoint subsets of $G$, such that the union of all the subsets is equal to the edgeset of G, then this is a decomposition. If such a ...
1
vote
2answers
66 views

Maximum subgraph edge distance greater than given number

I have a weighted graph G with approximately 75000 nodes. I would like to find subgraph G' induced on a subset of nodes, such that all edge weights in G' are greater than a given constant C and the ...
7
votes
1answer
410 views

A matching that covers vertices with maximum degree

We have a graph G with maximum degree $\Delta$. The induced subgraph on vertices with degree equal to $\Delta$ is a bipartite graph (while the original graph is not). Prove that G has a matching that ...
1
vote
1answer
152 views

Subgraph isomorphism problem on 2d triangular lattices.

Is there an efficient (possibly probabilistic/approximate) algorithm for determining whether a particular graph is the subgraph of an infinite two dimensional triangular lattice? How about three ...
1
vote
1answer
501 views

Minimum spanning subgraph with at least one incoming and one outgoing edge

Given a single-component, directed acyclic graph with one source (vertex with only outgoing edges) and one sink (vertex with only incoming edges), I'd like to find a minimum spanning subgraph which ...
1
vote
1answer
328 views

almost-bipartite nearly-isolated subgraphs

I am looking for examples/families of graphs with the following (maybe vague-sounding at first) property: the graph $G$ has a relatively large subgraph $B$ such that $B$ is bipartite-plus-a-few-edges ...