Discrete Mathematics, Volume 306

Volume 306, Number 1, 28 January 2006

Contributions

• 
  Sukumar Das Adhikari, Yong-Gao Chen, John B. Friedlander, Sergei Konyagin, Francesco Pappalardi:
  Contributions to zero-sum problems. 1-10
• 
  Tamara Burton, David P. Sumner:
  Domination dot-critical graphs. 11-18
• 
  Zhibo Chen:
  On integral sum graphs. 19-25
• 
  Matt DeVos, Rui Xu, Gexin Yu:
  Nowhere-zero Z₃-flows through Z₃-connectivity. 26-30
• 
  Melodie Fehr, Shonda Gosselin, Ortrud R. Oellermann:
  The metric dimension of Cayley digraphs. 31-41
• 
  John C. Galati:
  A group extensions approach to affine relative difference sets of even order. 42-51
• 
  Gennian Ge:
  Resolvable group divisible designs with block size four and index three. 52-65
• 
  Seth Kleinerman:
  Bounds on the forcing numbers of bipartite graphs. 66-73
• 
  Cheng Yeaw Ku, Imre Leader:
  An Erd˝s-Ko-Rado theorem for partial permutations. 74-86
• 
  Weiqi Luo, Zhi-Hong Chen, Wei-Guo Chen:
  Spanning trails containing given edges. 87-98
• 
  E. Maistrelli, D. B. Penman:
  Some colouring problems for Paley graphs. 99-106
• 
  Primoz Potocnik, Mateja Sajna:
  On almost self-complementary graphs. 107-123
• 
  Yunqing Xu, Yanxun Chang:
  Existence of r-self-orthogonal Latin squares. 124-146

Notes

• 
  Hiroyuki Nakasora:
  A construction of non self-orthogonal designs. 147-152
• 
  Wasin So:
  Integral circulant graphs. 153-158
• 
  Jun-Ming Xu, Chao Yang:
  Connectivity of Cartesian product graphs. 159-165
• 
  Raphael Yuster:
  Decomposing oriented graphs into transitive tournaments. 166-170

Volume 306, Number 2, 6 February 2006

Contributions

• 
  Gautam Appa, Dimitris Magos, Ioannis Mourtos, Jeannette C. M. Janssen:
  On the orthogonal Latin squares polytope. 171-187
• 
  José Cáceres, M. Carmen Hernando, Mercè Mora, Ignacio M. Pelayo, María Luz Puertas, Carlos Seara:
  On geodetic sets formed by boundary vertices. 188-198
• 
  Eva Ferrara Dentice:
  On finite matroids with two more hyperplanes than points. 199-209
• 
  Joan Gimbert, Nacho López, Mirka Miller, Joseph F. Ryan:
  Characterization of eccentric digraphs. 210-219
• 
  Hirobumi Mizuno, Iwao Sato:
  Bartholdi zeta functions of some graphs. 220-230
• 
  Marek Niezgoda:
  Bifractional inequalities and convex cones. 231-243
• 
  Andrew Schultz:
  On a modification of a problem of Bialostocki, Erdos, and Lefmann. 244-253
• 
  Sherman K. Stein, Sándor Szabó:
  The number of distinct symbols in sections of rectangular arrays. 254-261
• 
  Wei-Fan Wang:
  Edge-partitions of graphs of nonnegative characteristic and their game coloring numbers. 262-270

Notes

• 
  Frank Gurski:
  Characterizations for co-graphs defined by restricted NLC-width or clique-width operations. 271-277
• 
  Hideo Komuro, Kiyoshi Ando, Atsuhiro Nakamoto:
  Tight quadrangulations on the sphere. 278-283
• 
  Lian-Cui Zuo, Jianliang Wu, Jia-Zhuang Liu:
  The vertex linear arboricity of distance graphs. 284-289

Errata

• 
  Nawarat Ananchuen, Michael D. Plummer:
  Errata to "Matching properties in domination critical graphs" [Discrete Math 277 (2004) 1-13]. 291
• 
  Nawarat Ananchuen, Michael D. Plummer:
  Erratum to: "Some results related to the toughness of 3-domination critical graphs" [Discrete Math 272 (2003) 5-15]. 292

Volume 306, Number 3, 28 February 2006

Minimal Separation and Minimal Triangulation

• 
  Anne Berry, Jean R. S. Blair, Geneviève Simonet:
  Preface. 293
• 
  Pinar Heggernes:
  Minimal triangulations of graphs: A survey. 297-317
• 
  Anne Berry, Pinar Heggernes, Yngve Villanger:
  A vertex incremental approach for maintaining chordality. 318-336
• 
  Hans L. Bodlaender, Arie M. C. A. Koster:
  Safe separators for treewidth. 337-350
• 
  L. Sunil Chandran, Fabrizio Grandoni:
  A linear time algorithm to list the minimal separators of chordal graphs. 351-358
• 
  L. Sunil Chandran, Telikepalli Kavitha:
  The treewidth and pathwidth of hypercubes. 359-365
• 
  Dieter Kratsch, Jeremy P. Spinrad:
  Minimal fill in O(n^2.69) time. 366-371
• 
  Frédéric Mazoit:
  Listing all the minimal separators of a 3-connected planar graph. 372-380
• 
  Stavros D. Nikolopoulos, Leonidas Palios:
  Minimal separators in P₄-sparse graphs. 381-392
• 
  Yngve Villanger:
  Lex M versus MCS-M. 393-400

Volume 306, Number 4, 6 March 2006

Contributions

• 
  Josep M. Brunat, Antonio Montes:
  On polynomial digraphs. 401-412
• 
  Severino Villanueva Gervacio, Hiroshi Maehara:
  Partial order on a family of k-subsets of a linearly ordered set. 413-419
• 
  Mark Huber:
  Fast perfect sampling from linear extensions. 420-428
• 
  R. S. Manikandan, P. Paulraja:
  C_p-decompositions of some regular graphs. 429-451

Communications

• 
  Vahan V. Mkrtchyan:
  A note on minimal matching covered graphs. 452-455
• 
  Vahan V. Mkrtchyan:
  On trees with a maximum proper partial 0-1 coloring containing a maximum matching. 456-459

Notes

• 
  Stanislav Busygin, Dmitrii V. Pasechnik:
  On NP-hardness of the clique partition - Independence number gap recognition and related problems. 460-463
• 
  Jin Ho Kwak, Ju-Mok Oh:
  Constructing one-regular graphs of valency 4k with non-cyclic vertex stabilizer. 464-468

Volume 306, Number 5, 28 March 2006

Contributions

• 
  Dominique Barth, Hervé Fournier:
  A degree bound on decomposable trees. 469-477
• 
  David T. Branson:
  Stirling number representations. 478-494
• 
  Denis Cornaz, Jean Fonlupt:
  Chromatic characterization of biclique covers. 495-507
• 
  Andrew D. King:
  Generating indecomposable permutations. 508-518
• 
  HoKyu Lee:
  Double perfect partitions. 519-525
• 
  Fred M. Hoppe:
  Improving probability bounds by optimization over subsets. 526-530

Communications

• 
  Lars-Daniel Öhman:
  The intricacy of avoiding arrays is 2. 531-532

Notes

• 
  Jianguo Qian:
  Degree complete graphs. 533-537

Volume 306, Number 6, 6 April 2006

• 
  Camino Balbuena, Ewan Barker, Kinkar Chandra Das, Yuqing Lin, Mirka Miller, Joseph F. Ryan, Slamin, Kiki A. Sugeng, Michal Tkác:
  On the degrees of a strongly vertex-magic graph. 539-551
• 
  Eric S. Egge:
  Restricted signed permutations counted by the Schröder numbers. 552-563
• 
  Toufik Mansour, Sherry H. F. Yan, Laura L. M. Yang:
  Counting occurrences of 231 in an involution. 564-572
• 
  Mickaël Montassier, André Raspaud, Weifan Wang:
  Bordeaux 3-color conjecture and 3-choosability. 573-579
• 
  Suk Jai Seo, Peter J. Slater:
  Competition-reachability of a graph. 580-590
• 
  Andrey A. Dobrynin, Leonid S. Melnikov:
  Counterexamples to Grötzsch-Sachs-Koester's conjecture. 591-594
• 
  Flavia Bonomo:
  Self-clique Helly circular-arc graphs. 595-597
• 
  Thomas Britz:
  On P-weight and P-distance inequalities. 598-599
• 
  Mike J. Grannell, Terry S. Griggs, Martin Knor, Jozef Sirán:
  Triangulations of orientable surfaces by complete tripartite graphs. 600-606
• 
  Kenji Kimura:
  Factors and vertex-deleted subgraphs. 607-611
• 
  Vladimir Nikiforov:
  The smallest eigenvalue of K_r-free graphs. 612-616

Volume 306, Number 7, 28 April 2006

• 
  Mekkia Kouider, Manouchehr Zaker:
  Bounds for the b-chromatic number of some families of graphs. 617-623
• 
  Piotr Sniady:
  Asymptotics of characters of symmetric groups, genus expansion and free probability. 624-665
• 
  Thomas Böhme, Martin Knor, Ludovít Niepel:
  Linkability in iterated line graphs. 666-669
• 
  Kefeng Diao, Guizhen Liu, Dieter Rautenbach, Ping Zhao:
  A note on the least number of edges of 3-uniform hypergraphs with upper chromatic number 2. 670-672
• 
  Henry A. Kierstead:
  Weak acyclic coloring and asymmetric coloring games. 673-677
• 
  Imre Leader, Klas Markström:
  Uncountable families of vertex-transitive graphs of finite degree. 678-679
• 
  Manoel Lemos:
  Matroids with few non-common bases. 680-687
• 
  Haruhide Matsuda:
  Fan-type results for the existence of [a, b]-factors. 688-693
• 
  Øystein J. Rødseth:
  Enumeration of M-partitions. 694-698
• 
  Khaled Salem, Sandi Klavzar, Ivan Gutman:
  On the role of hypercubes in the resonance graphs of benzenoid graphs. 699-704
• 
  Zhao Zhang, Jixiang Meng:
  Semi-hyper-connected edge transitive graphs. 705-710

Volume 306, Numbers 8-9, 1 May 2006

Contributions

• 
  Fabrizio Caselli, Mario Marietti:
  Formulas for multi-parameter classes of Kazhdan-Lusztig polynomials in G(n). 711-725
• 
  Gary Chartrand, Sin-Min Lee, Ping Zhang:
  Uniformly cordial graphs. 726-737
• 
  Han Hyuk Cho, Suh-Ryung Kim, Jung Yeun Lee:
  On the graph inequality theta_E(G) geq theta_E(G^m). 738-744
• 
  Ellen E. Eischen:
  Decomposition of almost complete tripartite graphs into two isomorphic factors of fixed diameter. 745-761
• 
  Roland Häggkvist, Klas Markström:
  Cycle double covers and spanning minors II. 762-778
• 
  Edita Mácajová, Martin Skoviera:
  Irreducible snarks of given order and cyclic connectivity. 779-791
• 
  Yu-Ping Tsao, Gerard J. Chang:
  Profile minimization on products of graphs. 792-800
• 
  Inna Zverovich, Igor E. Zverovich:
  Bipartite bihypergraphs: A survey and new results. 801-811

Notes

• 
  Joseph E. Bonin:
  Extending a matroid by a cocircuit. 812-819
• 
  Kelli Carlson, Mike Develin:
  On the bondage number of planar and directed graphs. 820-826
• 
  David Eisenstat, Gary Gordon:
  Non-isomorphic caterpillars with identical subtree data. 827-830
• 
  Tobias Gerlach, Frank Göring, Jochen Harant, Michal Tkác:
  On cycles through specified vertices. 831-835
• 
  Charles H. Jepsen, Ming Gu:
  Dissections of p: q rectangles into 13 p: q rectangular elements. 836-842
• 
  Andrzej P. Kisielewicz, Krzysztof Przeslawski:
  On the number of minimal partitions of a box into boxes. 843-846
• 
  Imre Leader, Paul A. Russell:
  Consistency for partition regular equations. 847-850

Volume 306, Numbers 10-11, 28 May 2006

35th Special Anniversary Issue

• 
  Peter L. Hammer:
  Preface. 851-852
• 
  Paul Erdös, Amram Meir, Vera T. Sós, Paul Turán:
  On some applications of graph theory, I. 853-866
• 
  László Lovász:
  Normal hypergraphs and the perfect graph conjecture. 867-875
• 
  Haim Hanani, Dwijendra K. Ray-Chaudhuri, Richard M. Wilson:
  On resolvable designs. 876-885
• 
  Vasek Chvátal:
  Edmonds polytopes and a hierarchy of combinatorial problems. 886-904
• 
  Richard P. Stanley:
  Acyclic orientations of graphs. 905-909
• 
  Vasek Chvátal:
  Tough graphs and hamiltonian circuits. 910-917
• 
  László Babai:
  Automorphism groups of graphs and edge-contraction. 918-922
• 
  Paul Erdös, Daniel J. Kleitman:
  Extremal problems among subsets of a set. 923-931
• 
  W. T. Tutte:
  Spanning subgraphs with specified valencies. 932-938
• 
  Andries E. Brouwer, Alexander Schrijver, Haim Hanani:
  Group divisible designs with block-size four. 939-947
• 
  Béla Bollobás, Andrew Thomason:
  Set colourings of graphs. 948-952
• 
  Oleg V. Borodin:
  On acyclic colorings of planar graphs. 953-972
• 
  Alexander Schrijver, Paul D. Seymour:
  Solution of two fractional packing problems of Lovász. 973-978
• 
  Paul D. Seymour:
  Disjoint paths in graphs. 979-991
• 
  Philippe Flajolet:
  Combinatorial aspects of continued fractions. 992-1021
• 
  Ira M. Gessel:
  A q-analog of the exponential formula. 1022-1031
• 
  János Komlós, Endre Szemerédi:
  Limit distribution for the existence of Hamiltonian cycles in a random graph. 1032-1038
• 
  Doron Zeilberger, David M. Bressoud:
  A proof of Andrews' q-Dyson conjecture. 1039-1059
• 
  Luc Teirlinck:
  Non-trivial t-designs without repeated blocks exist for all t. 1060-1067
• 
  Noga Alon, Fan R. K. Chung:
  Explicit construction of linear sized tolerant networks. 1068-1071
• 
  Doron Zeilberger:
  A fast algorithm for proving terminating hypergeometric identities. 1072-1075
• 
  Margit Voigt:
  List colourings of planar graphs. 1076-1079
• 
  Sergey Fomin, Curtis Greene:
  Noncommutative Schur functions and their applications. 1080-1096

Volume 306, Number 12, 28 June 2006

Contributions

• 
  Ahmed Ainouche, Serge Lapiquonne:
  Hamilton connectedness and the partially square graphs. 1097-1104
• 
  Gergely Ambrus, János Barát:
  A contribution to queens graphs: A substitution method. 1105-1114
• 
  Fethi Ben Saïd, Houda Lahouar, Jean-Louis Nicolas:
  On the counting function of the sets of parts A such that the partition function p(A, n) takes even values for n large enough. 1115-1125
• 
  Simon R. Blackburn, Igor E. Shparlinski:
  Character sums and nonlinear recurrence sequences. 1126-1131
• 
  Chiuyuan Chen, Chih-Shin Hung, Wen-Shiang Tang:
  On the existence of hyper-L triple-loop networks. 1132-1138
• 
  Ming-You Chen, Frank K. Hwang, Chih-Hung Yen:
  Tessellating polyominos in the plane. 1139-1144
• 
  Nicolas Lichiardopol:
  Independence number of de Bruijn graphs. 1145-1160
• 
  Toufik Mansour:
  Restricted even permutations and Chebyshev polynomials. 1161-1176
• 
  Romeo Rizzi:
  Acyclically pushable bipartite permutation digraphs: An algorithm. 1177-1188
• 
  Ngo Dac Tuan:
  Hypergraphical t-designs. 1189-1197
• 
  Lutz Volkmann:
  On cycles in regular 3-partite tournaments. 1198-1206
• 
  Aifeng Yang, Jinjiang Yuan:
  Partition the vertices of a graph into one independent set and one acyclic set. 1207-1216
• 
  Roger K. Yeh:
  A survey on labeling graphs with a condition at distance two. 1217-1231

Communications

• 
  Edwin Soedarmadji:
  Latin hyper