|
2016-present
-
A random graph model for clustering graphs
,
Proceeding of the 18th Workshop on Algorithms and Models for the Web Graph (WAW 2023),
Lecture Notes in Computer Science 13894, Springer, 2023,
pp. 112-126,
(with Nick Sieger).
-
Quasi-random influences of Boolean functions
, preprint,
(with Nick Sieger).
-
Fan-complete Ramsey numbers
, preprint,
(with Qizhong Lin).
-
Forest formulas of discrete Green's functions, J. of Graph Theory, 102, (2023), 556-577,
(with Ji Zeng).
-
Regularity lemmas for clustering graphs, Advances in Applied Math. 126 (2021) article 101961.
-
The spectral gap of graphs arising from substring reversals, The Electronic J. of Combinatorics, 24, no. 3 (2017), #P.3.4,
(with J. Tobin)
-
A strong Harnack inequality for graphs,
Comm. Analysis and Geometry, 25, no. 3, (2017), 557--588,
(with S.-T. Yau).
-
Extreme values of the stationary distribution of random walks on directed graphs
,
Advance in Applied Math., 81, (2016), 128--155,
(with Sinan Aksoy and Xing Peng).
-
A generalized Alon-Boppana bound and weak Ramanujan graphs, Electronic Journal of Combinatorics, 23, (2016), Paper #3.4, (20 pages).
The
version in E-JC.
-
Curvature aspects of graphs,
Proc. of AMS, 145 (2017), 2033--2042,
(with F. Bauer, Y. Lin and Y. Liu).
-
Decomposition of random graphs into complete bipartite graphs , SIAM J. Discrete Math., 30, no. 1, (2016), 296--310,
(with X. Peng).
2011-2015
-
Edge flipping in the complete graphs, Advances in Appl. Math. 69 (2015), 46--64,
(with S. Butler, J. Cummings and R. L. Graham).
-
Discrepancy inequalities for directed graphs
,
Discrete Applied Mathematics, 176 (2014) 30-42,
(with F. Kenter).
-
Harnack inequalities for graphs with non-negative Ricci curvature
,
J. Math. Anal. Appl. 415 (2014), 25 -- 32,
(with Yong Lin and S.-T. Yau).
-
From quasirandom graphs to graph limits and graphlets
,
Advances in Applied Math. 56 (2014),
135--174.
-
A local clustering algorithm for connection graphs
,
WAW 2013, LNCS 8305, 203--219,
(with Mark Kempton).
The journal version appeared in Internet Math., 11 (2015), 333-351.
-
Spectral clustering of graphs with general degrees in the extended planted partition model
,
COLT 2012,
Journal of Machine Learning Research, (2012), 1--23,
(with K. Chaudhuri and A. Tsiatas).
-
Edge flipping in graphs,
Advances in Applied Mathematics, 48 (2012) 37--63,
(with Ron Graham).
-
On the spectra of general random graphs,
Electronic Journal of Combinatorics, 18(1),
(2011), P215, 14 pages,
(with M. Radcliffe).
2006-2010
Back to top
-
PageRank and random walks on graphs
,
Fete of Combinatorics and Computer Science, (G. O. H. Katona, A. Schrijver and T. Szonyi, Eds.),
Springer, Berlin, (2010), 43--62,
(with Wenbo Zhao).
-
Braess's paradox in large sparse graphs,
WINE 2010, LNCS 6484, 194--208,
(with Stephen J. Young).
-
A whirlwind tour of random graphs
,
a survey article in Encyclopedia on Complex Systems, Springer, 2008.
-
Quasi-random graphs with
given degree sequences,
Random Structures and Algorithms, 12 (2008), 1--19,
(with R. L. Graham).
-
Local partitioning for directed graphs using PageRank
,
WAW2007, 166--178,
(with R. Andersen and Kevin Lang).
The full paper is in Internet Mathematics, 5 (2008), 3--22.
-
Random walks and local cuts
in graphs,
Linear Algebra and its Applications, 423 (2007), 22--32.
-
Weighted Laplacians and the Sigma function of a graph,
Quantum Graphs and their Applications,
(B. Berkolaiko et. al. eds), Contemporary Math., AMS, Providence, RI,
93-107, 2006
(with Ross Richardson).
-
The diameter and
Laplacian eigenvalues of directed graphs,
Electronic Journal of Combinatorics 13 (2006), N4, 6 pp.
-
Complex Graphs and Networks,
CBMS Number 107, AMS Publications, 2006, vii+264pp.,
(with L. Lu)
2001-2005
Back to top
-
Laplacians
and the Cheeger inequality for
directed graphs,
Annals of Combinatorics, 9 (2005), 1--19.
-
Drawing power law graphs,
Proceedings Graph Drawing, New York, 2004, 12--17,
(with Reid Andersen, L. Lu).
Paper version, Drawing power law graphs
using a local/global decomposition, appeared in Algorithmica
47 (2007), 379--397.
-
Coupling online and offline analyses for random power law graphs,
Internet Mathematics, 1 (2004), 409--461,
(with Lincoln Lu).
-
The small world phenomenon in hybrid power law graphs,
Complex Networks, (Eds. E. Ben-Naim et. al.), Springer-Verlag, (2004), 89--104,
(with Lincoln Lu).
- Finding Favorites,
Electronic Colloquium on Computational Complexity, Report No. 78 (2003),
(with Ron Graham, Jia Mao and Andrew Yao).
-
Eigenvalues of random power law graphs,
Annals of Combinatorics 7 (2003), 21--33,
(with Lincoln Lu and Van Vu).
-
The spectra of random graphs with given expected degrees,
short version,
Proceedings of National Academy of Sciences 100, no. 11, (2003), 6313--6318,
long version
(with full proofs) Internet Mathematics 1 (2004), 257--275,
(with Lincoln Lu and Van Vu).
-
The average distances in random graphs with given expected degrees,
abstract,
paper (short version),
Proc. National Academy of Sciences 99, no. 25, (December, 2002), 15879--15882,
paper (long version)
,
Internet Mathematics 1 (2003), 91--113,
(with L. Lu).
-
Sparse quasi-random graphs,
abstract,
Combinatorica 22 (2002), 217--244,
(with Ronald Graham)
-
Connected components in random graphs with given expected degree sequences,
abstract,
Annals of Combinatorics 6 (2002), 125-145,
(with L. Lu).
-
Random evolution of massive graphs,
abstract,
Handbook of Massive Data Sets, (Eds. James Abello et al.), Kluwer Academic
Publishers, (2002), 97--122,
extended abstract appeared in FOCS 2001, 510--519,
(with W. Aiello and L. Lu).
-
The diameter of sparse random graphs,
abstract,
Advances in Applied Math. 26 (2001), 257--279,
(with Linyuan Lu).
1996-2000
Back to top
-
Higher eigenvalues and isoperimetric inequalities on
Riemannian manifolds and graphs,
Communications on Analysis and Geometry 8, (2000), 969--1026,
(with A. Grigor'yan and S.-T. Yau).
-
A random graph model for massive graphs,
abstract,
Proceedings of the
Thirtysecond Annual ACM Symposium on Theory of Computing
(2000),
171--180,
(with Bill Aiello and Linyuan Lu).
The complete paper version
has a different title
A random graph model for power law graphs,
Experimental Math. 10 (2001), 53--66.
-
Spanning trees in subgraphs of lattices,
Comtempory Math. 245, Amer. Math. Soc., Providence, R. I., 1999, 201--219.
-
Logarithmic Sobolev techniques for random walks on graphs,
Emerging Applications of Number Theory, IMA Volumes in Math. and its Applications
109 (eds. D. A. Hejhal et. al.), 175--186, Springer, 1999.
- Isoperimetric inequalities for Cartesian products of graphs,
Combinatorics, Probability and Computing 7 (1998), 141--148,
(with Prasad Tetali).
-
Erdos on Graphs. His Legacy of Unsolved Problems,
A. K. Peters, Wellesley, MA, 1998, xiv+142 pp.,
(with Ron Graham).
-
Eigenvalue inequalities for graphs and convex subgraphs,
Communications on Analysis and Geometry 5 (1997), 575--623,
(with S.-T. Yau).
-
Eigenvalues and diameters for manifolds and graphs,
Tsing Hua Lectures on Geometry and Analysis,
International Press, Cambridge, Massachusetts, 1997, 79--106,
(with A. Grigor'yan and S.-T. Yau).
-
Laplacians of graphs and Cheeger's inequalities,
in Combinatorics, Paul Erdos is eighty, Vol. 2 (Keszthely, 1993),
Bolyai Math.
Soc., Budapest, 1996, 157--172.
1991-1995
Back to top
-
Pebbling a chessboard,
Amer. Math. Monthly 102 (1995), 113--123,
(with Ron Graham, John Morrison and Andrew Odlyzko).
-
A Harnack inequality for homogeneous graphs and subgraphs,
Communications on Analysis and Geometry 2
(1994), 627--640,
also in Turkish J. Math. 19 (1995), 273--290,
(with S.-T. Yau).
-
Eigenvalues of graphs,
Proceedings of the International Congress of Mathematicians (Zurich, 1994),
Birkhäuser Verlag, Berlin, 1333--1342.
-
Eigenvalues of graphs and Sobolev inequalities,
Combinatorics, Probability and Computing 4 (1995), 11--26,
(with S.-T. Yau).
-
Routing permutations on graphs via matchings,
SIAM J. Discrete Math. 7 (1994) 513--530,
(with Noga Alon and R. L. Graham).
-
Chordal completions of planar graphs,
J. of Comb. Th. (B) 62 (1994), 96--106,
(with David Mumford).
-
Even cycles in directed graphs,
SIAM J. Discrete Math. 7 (1994) 474--483,
(with Wayne Goddard and D. J. Kleitman).
-
The Laplacian of a hypergraph,
in Expanding graphs (Princeton, NY, 1992),
DIMACS Ser. Discrete Math. Theoret.
Comput. Sci., 10, Amer. Math. Soc., Providence, RI, 1993, 21--36.
-
Chordal completions of grids and planar graphs,
in Planar graphs (New Brunswick, NJ, 1991), DIMACS Ser. Discrete Math. Theoret.
Comput. Sci., 9, Amer. Math. Soc., Providence, RI, 1993, 37--40,
(with D. Mumford).
-
On hypergraphs having evenly distributed subhypergraphs,
Disc. Math. 111 (1993), 125--129,
(with Ron Graham).
-
A note on constructive lower bounds for the Ramsey numbers R(3,t),
J. Comb. Theory (B) 57 (1993), 150--155,
(with R. Cleve and P. Dagum).
-
Laplacian and vibrational spectra for homogeneous graphs,
J. Graph Theory 16 (1992), 605--627,
(with Shlomo Sternberg).
-
Cohomological aspects of hypergraphs,
Trans. Amer. Math. Soc. 334 (1992), 365--388,
(with R. L. Graham).
-
Subgraphs of a hypercube containing no small even cycles,
J. Graph Theory 16 (1992), 273--286.
-
Graphs with small diameter after edge deletion,
Discrete Applied Math. 37/38 (1992), 73--94.
-
Maximum cuts and quasirandom graphs,
in Random Graphs, John Wiley and Sons (1992), 23--33,
(with R.L. Graham).
-
Constructing random-like graphs,
Probabilistic Combinatorics and Its Applications, (B. Bollobas ed.), Amer. Math. Soc., Providence, (1991), 21--55.
-
Improved separators for planar graphs,
Graph Theory, Combinatorics, and Applications, John Wiley and Sons, (1991), 265--270.
-
Regularity lemmas for hypergraphs and quasi-randomness,
Random Structures and Algorithms 2 (1991), 241--252.
1986-1990
Back to top
-
Quasi-random classes of hypergraphs,
Random Structures and Algorithms 1 (1990), 363--382.
Corrigendum.
-
On graphs not containing prescribed induced subgraphs,
in A Tribute to Paul Erdos, Cambridge University Press (1990), 111--120,
(with R.L. Graham).
-
The Maximum number of edges in 2K2-free graphs of bounded degree,
Discrete Math. 81 (1990), 129--135,
(with A. Gyarfas, W. T. Trotter and Z. Tuza).
-
Universal graphs and induced-universal graphs,
J. Graph Theory 14 (1990) 443--454.
-
Quasi-random graphs,
a short
version appeared in Proc. Natl. Acad. Sci. USA, 85 (1988), 969--970,
a long
version
appeared in Combinatorica 9 (1989), 345--362,
(with R. L. Graham and R. M. Wilson).
-
Quasi-random hypergraphs,
Proc. Natl. Acad. Sci. USA 86 (1989), 8175--8177,
Long
version appeared in Random Structures
and Algorithms 1 (1990), 105--124,
(with R.L. Graham).
-
Diameters and eigenvalues,
J. of the Amer. Math. Soc. 2 (1989), 187--196.
-
Graphs with small bandwidth and cutwidth,
Discrete Math. 75 (1989), 113--119,
(with P.D. Seymour).
-
A dynamic location problem for graphs,
Combinatorica 9 (1989), 111--131,
(with R. L. Graham and M. Saks).
-
Universal graphs for
bounded-degree trees and planar graphs,
SIAM J. Discrete Math. 2 (1989), 145--155,
(with S. Bhatt, F. T. Leighton and A. L. Rosenberg).
-
On the fractional covering number of hypergraphs,
SIAM J. on Discrete Math. 1 (1988), 45--49,
(with Z. Furedi, M. R. Garey and R. L. Graham).
-
On induced subgraphs of the cube,
J. Comb. Th. (A) 49 (1988), 180--187,
(with Z. Furedi, R.L. Graham and P. Seymour).
-
Pursuit-evasion games on graphs,
J. Graph Theory 12 (1988), no. 2, 159--167,
(with J.E. Cohen and R.L. Graham).
-
Labelings of graphs,
Selected Topics in Graph Theory 3, Academic Press, San Diego, CA, 1988, 151--168.
-
The diameter of a cycle plus a random matching,
SIAM J. on Discrete Math. 1 (1988), 328--333.
(with B. Bollobás)
-
The maximum number of edges in a 3-graph not containing a given star,
Graphs and Combinatorics 3 (1987), 111--126,
(with P. Frankl).
-
Diameters of graphs:
old problems and new results,
Congressus Numerantium 60 (1987), 295--317.
-
Dynamic search in graphs,
Discrete Algorithms and Complexity (1987), 351--387,
(with R. L. Graham and M. Saks).
-
Highly irregular graphs,
J. Graph Theory 11 (1987), 235--249,
(with Yousef Alavi, Gary Chartrand, Paul Erdos, R. L. Graham and Ortrud R. Oellermann).
-
On unavoidable hypergraphs,
J. Graph Theory 11 (1987), 251--263,
(with P. Erdos).
-
Embedding graphs in books: a layout
problem with applications to VLSI design,
SIAM J. Algebraic Discrete Methods 8 (1987), no. 1, 33--58,
also in
Graph theory with applications
to algorithms and computer science (Kalamazoo, Mich., 1984), 175--188,
Wiley-Intersci. Publ., Wiley, New York, 1985,
(with F.T. Leighton and A.L. Rosenberg).
-
Monotone subsequences in (0,1)-matrices,
Graphs Combin. 2 (1986), no. 1, 31--36,
(with P.C. Fishburn and V.K. Wei).
-
Some intersection theorems for ordered sets
and graphs,
J. Combin. Theory Ser. (A) 43 (1986), no. 1, 23--37,
(with R.L. Graham, P. Frankl, and J.B. Shearer).
1981-1985
Back to top
-
On the addressing problem for directed graphs,
Graphs Combin. 1 (1985), no. 1, 41--50, (with R.L. Graham, and P.M. Winkler).
-
Strongly connected orientations of mixed multigraphs,
Networks 15 (1985), no. 4, 477--484, (with M.R. Garey and R.E. Tarjan).
-
Extremal subgraphs for two graphs,
J. Combin. Theory (B) 38 (1985), no. 3, 248--260, (with P. Erdös and J. Spencer).
-
Increasing sequences with nonzero
block sums and increasing paths in edge-ordered graphs,
Discrete Math. 50 (1984), no. 1, 15--28, (with A. R. Calderbank and D. Sturtevant).
-
Diameter bounds for altered graphs,
J. Graph Theory 8 (1984), no. 4, 511--534, (with M. R. Garey).
-
On unavoidable graphs,
Combinatorica 3 (1983), no. 2, 167--176, (with P. Erdös).
-
Unavoidable stars in 3-graphs,
J. Combin. Theory Ser. (A) 35 (1983), no. 3, 252--262.
-
On universal graphs for spanning trees,
Journal of London Math. Soc. 27 (1983), 203--211
(with R. L. Graham).
-
Edge-colored complete graphs with precisely colored subgraphs,
Combinatorica 3 (1983), no. 3-4, 315--324,
(with R.L. Graham).
-
On the decomposition of graphs into complete
bipartite subgraphs
Studies in Pure Mathematics Akadémiai Kiadó, Budapest, (1983) 95--101,
(with P. Erdös and J. Spencer).
-
On complete bipartite subgraphs contained in
spanning tree complements,
Studies in Pure Mathematics, (ed.-in-chief P. Erdös) Akadémiai Kiadó, Budapest, (1983)
83--90,
(with B. Bollobas and R. L. Graham).
-
Triangle-free graphs with restricted bandwidth,
Progress in graph theory (Waterloo, Ont., 1982), 175--190, Academic Press,
Toronto, ON, 1984,
(with W.T. Trotter, Jr.).
-
On the minimum dominating pair number of
a class of graphs,
Caribbean J. Math. 1 (1982), no. 2, 73--76,
(with R.L. Graham, E.J. Cockayne, and D.J. Miller).
-
Minimal decompositions of hypergraphs into mutually
isomorphic subhypergraphs,
J. Comb. Th. (A) 32 (1982), 241--251,
(with P. Erdös and R. L. Graham).
-
On graphs which contain all sparse graphs,
Annals of Discrete Math. 12 (1982), 21--26,
(with L. Babai, P. Erdös, R. L. Graham, and J. Spencer).
-
The number of relation graphs,
Bell Laboratories Internal Memorandum, 1982,
(with F. K. Hwang and D. H. Krantz).
-
Minimal decomposition of all graphs
with equinumerous vertices and edges into mutually isomorphic subgraphs,
Finite and infinite sets, Vol. I, II (Eger, 1981), 171--179, Colloq. Math.
Soc. János Bolyai 37, North-Holland, Amsterdam, 1984,
(with P. Erdös and R. L. Graham).
-
Some problems and results on labelings of graphs,
The Theory and Applications of Graphs (ed. G. Chartrand), John Wiley and Sons (1981), 255-264.
-
On the bandwidths of a graph and its complement,
The Theory and Applications of Graphs (ed. G. Chartrand), John Wiley and Sons (1981), 243-253,
(with P. Z. Chinn, P. Erdös and R. L. Graham).
-
On trees containing all small trees,
The Theory of Applications of Graphs (ed. by G. Chartrand) John Wiley and
Sons, (1981) 265--272, (with R. L. Graham and D. Coppersmith).
-
Minimal decomposition of graphs into mutually
isomorphic subgraphs,
Combinatorica 1 (1981), 13--24,
(with P. Erdös and R. L. Graham).
-
On the decompositions of graphs,
SIAM J. Alg. Disc. Methods 2 (1981), 1--12.
-
Rotatable graceful graphs,
Ars Combinatoria 11 (1981), 239--250,
(with F. K. Hwang).
1975-1980
Back to top
-
On the coverings of graphs,
Discrete Math. 30 (1980), 89--93.
-
On universal graphs,
Annals of the New York Academy of Sciences 319 (1979), 136--140,
(with R. L. Graham).
-
Minimal decompositions of two graphs into pairwise isomorphic subgraphs,
Proceedings of the 10th Southeastern Conf. on Comb., Graph Theory and Computing (1979), 3--18,
(with P. Erdos, R.L. Graham, S.M. Ulam and F.F. Yao).
-
On blocking probabilities for a class of linear
graphs,
Bell Systems Tech. J. 57 (1978), 2915--2925,
(with F. K. Hwang).
-
A generalization of Takagi's Theorem on
optimal channel graphs,
Bell System Tech. J. 57 (1978), 171--178,
(with F. K. Hwang).
-
On partitions of graphs into trees,
Discrete Math. 23 (1978), 23-30.
-
On graphs which contain all small trees,
J. Comb. Th. (B) 24 (1978), 14--23,
(with R. L. Graham).
-
On graphs which contain all small trees II,
Colloquia Mathematica Societatis János Bolyai, Keszthely, Hungary, (1976), 213--223,
(with R. L. Graham and N. Pippenger).
1973-1975
Back to top
-
On multicolor Ramsey numbers for complete bipartite
graphs,
J. Comb. Th. (B) 18 (1975), 164--169,
(with R. L. Graham).
-
Optimal Rearrangeable graphs,
Bell System Tech. J. 54 (1975), 1647--1661.
-
On triangular and cyclic Ramsey numbers with
k colors,
Graphs and Combinatorics, Lecture Notes, No. 406, (1974), 236--242, Springer-Verlag, New York.
|