1,201 reputation
47
bio website york.cuny.edu/~malk
location New York, NY
age
visits member for 4 years
seen Aug 5 '11 at 17:39

I am a mathematician interested in geometry, combinatorics, mathematical modeling, and mathematics education.


Sep
24
awarded  Autobiographer
Sep
8
awarded  Yearling
Sep
8
awarded  Yearling
Sep
8
awarded  Yearling
Sep
9
awarded  Yearling
Aug
5
answered Is any chordal graph an incomparability graph?
Jul
7
comment Results regarding Bounded Diameter Minimum Spanning Tree
Does this paper have any ideas that might be of use: math.tau.ac.il/~hassin/diameter_95.pdf
Mar
29
awarded  Nice Answer
Mar
26
answered What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?
Mar
26
answered Conjectures implying Four Color Theorem
Feb
19
comment Is this graph transformation unique up to isomorphism? [Answer:NO]
Truncation is a natural operation on polytopes but I am not sure this is necessarily a good name for something more general. Another natural operation polytopes is an edge shave. On a 3-valent 3-polytope this replaces an edge by a 4-gon.
Feb
19
comment Is this graph transformation unique up to isomorphism? [Answer:NO]
Putting to the side the issues about isomorphism, the graph operation suggested by the top diagram, when applied to planar 3-connected graphs (which are the 3-polytopal graphs), corresponds to the idea of truncation of a vertex of the polytope associated with the graph. In particular, the new graph will be planar and 3-connected and sometimes reflects nice properties of the original polytope. For example, if one has a hamiltonian polytope and truncates a 3-valent vertex one gets a new 3-polytope which still has a hamiltonian circuit.
Feb
17
answered Why does the Fibonacci sequence produce a worst-case Huffman encoding?
Jan
15
awarded  Commentator
Jan
15
comment Complexity of Max Bisection on cubic planar graphs?
By "crossing edges" do you mean the edges whose endpoints are in both sets making up the bisection?
Dec
31
comment Coloring Planar Graphs
You might look at these two papers: google.com/… and google.com/…
Dec
10
comment Dijkstra parallelization
Is what you are describing above the same as what was based on an idea of Steve Hedetniemi as described here?: highered.mcgraw-hill.com/sites/dl/free/0072880082/299355/… and also here: deepblue.lib.umich.edu/handle/2027.42/59763
Dec
7
answered Classes of graphs with easy Hamiltonian cycle but NP-hard TSP
Dec
6
answered Can we partition NP-complete problem into finite number of polynomially solvable problems?
Dec
5
answered About properties of adjacency matrix when a graph is planar