Discrete Applied Mathematics, Volume 159

Volume 159, Number 1, January 2011

Contributions

• 
  Irénée Briquel, Pascal Koiran, Klaus Meer:
  On the expressive power of CNF formulas of bounded tree- and clique-width. 1-14
• 
  Brian C. Dean, Sandra Mitchell Hedetniemi, Stephen T. Hedetniemi, Jason Lewis, Alice A. McRae:
  Matchability and k-maximal matchings. 15-22
• 
  Flavio Guiñez, Martín Matamala, Stéphan Thomassé:
  Realizing disjoint degree sequences of span at most two: A tractable discrete tomography problem. 23-30
• 
  Arne Bang Huseby:
  Oriented matroid systems. 31-45
• 
  Moo Young Sohn, Dongseok Kim, Young Soo Kwon, Jaeun Lee:
  On the existence problem of the total domination vertex critical graphs. 46-52
• 
  Daniel Cosmin Porumbel, Jin-Kao Hao, Pascale Kuntz:
  An efficient algorithm for computing the distance between close partitions. 53-59
• 
  Clara Inés Betancur Velasquez, Flavia Bonomo, Ivo Koch:
  On the b-coloring of P₄-tidy graphs. 60-68
• 
  Rundan Xing, Bo Zhou:
  On the revised Szeged index. 69-78

Notes

• 
  Jochen Harant, Dieter Rautenbach:
  Independence in connected graphs. 79-86
• 
  Nicolas Roussel:
  Total choosability of planar graphs with maximum degree 4. 87-89

Volume 159, Numbers 2-3, January 2011

Contributions

• 
  Camino Balbuena, Pedro García-Vázquez, Luis Pedro Montejano:
  Superconnectivity of graphs with odd girth g and even girth h. 91-99
• 
  Kim A. S. Factor, Sarah K. Merz:
  The (1, 2)-step competition graph of a tournament. 100-103
• 
  Michael A. Henning, Nader Jafari Rad:
  Total domination dot-critical graphs. 104-111
• 
  Alexander K. Kelmans:
  Packing 3-vertex paths in claw-free graphs and related topics. 112-127
• 
  Richard Krueger, Geneviève Simonet, Anne Berry:
  A General Label Search to investigate classical graph search algorithms. 128-142
• 
  Anders Sune Pedersen, Dieter Rautenbach, Friedrich Regen:
  Lower bounds on the independence number of certain graphs of odd girth at least seven. 143-151

Notes

• 
  Meysam Alishahi:
  On the dynamic coloring of graphs. 152-156
• 
  Jianfeng Hou, Bin Liu, Guizhen Liu, Jianliang Wu:
  Total coloring of planar graphs without 6-cycles. 157-163

Volume 159, Number 4, February 2011

Contributions

• 
  Raquel S. F. Bravo, Sulamita Klein, Loana Tito Nogueira, Fábio Protti:
  Characterization and recognition of P₄-sparse graphs partitionable into k independent sets and l cliques. 165-173
• 
  Csilla Bujtás, E. Sampathkumar, Zsolt Tuza, L. Pushpalatha, R. C. Vasundhara:
  Improper C-colorings of graphs. 174-186
• 
  Giulia Galbiati, Romeo Rizzi, Edoardo Amaldi:
  On the approximability of the minimum strictly fundamental cycle basis problem. 187-200
• 
  Enkelejd Hashorva:
  Asymptotics of the convex hull of spherically symmetric samples. 201-211
• 
  Shangwei Lin, Shiying Wang, Chunfang Li:
  Panconnectivity and edge-pancyclicity of k-ary n-cubes with faulty elements. 212-223
• 
  José M. Sigarreta Almira, Ismael González Yero, Sergio Bermudo, Juan Alberto Rodríguez-Velázquez:
  Partitioning a graph into offensive k-alliances. 224-231
• 
  Yingqian Wang, Qian Wu, Liang Shen:
  Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable. 232-239

Notes

• 
  Xiang-Feng Pan, Ning-Ning Lv:
  Sharp bounds of the zeroth-order general Randic index of bicyclic graphs with given pendent vertices. 240-245
• 
  Zdenek Ryjácek, Gerhard J. Woeginger, Liming Xiong:
  Hamiltonian index is NP-complete. 246-250
• 
  Karin Thörnblad, Michael Patriksson:
  A note on the complexity of flow-shop scheduling with deteriorating jobs. 251-253

Volume 159, Number 5, March 2011

Special Section: Boolean and Pseudo-Boolean Functions

• 
  Frank Markham Brown:
  On the suppression of variables in Boolean equations. 255-258
• 
  Jeffrey C. Jackson, Homin K. Lee, Rocco A. Servedio, Andrew Wan:
  Learning random monotone DNF. 259-271

Contributions

• 
  Philippe Baptiste, Jacques Carlier, Alexander V. Kononov, Maurice Queyranne, Sergey Sevastyanov, Maxim Sviridenko:
  Properties of optimal schedules in preemptive shop scheduling. 272-280
• 
  sarah-marie belcastro, Michael Young:
  1-factor covers of regular graphs. 281-287
• 
  Flavia Bonomo, Guillermo Durán, Javier Marenco, Mario Valencia-Pabon:
  Minimum sum set coloring of trees and line graphs of trees. 288-294
• 
  Pavel Chebotarev:
  A class of graph-geodetic distances generalizing the shortest-path and the resistance distances. 295-302
• 
  Christine T. Cheng, Ichiro Suzuki:
  Weak sense of direction labelings and graph embeddings. 303-310
• 
  Vladimir Gurvich:
  On exact blockers and anti-blockers, Δ-conjecture, and related problems. 311-321
• 
  Hovhannes A. Harutyunyan, Pavol Hell, Arthur L. Liestman:
  Messy broadcasting - Decentralized broadcast schemes with limited knowledge. 322-327
• 
  Jonelle Hook, Garth Isaak:
  Star-critical Ramsey numbers. 328-334
• 
  Ville Junnila, Tero Laihonen:
  Identification in Z2 using Euclidean balls. 335-343
• 
  Martin Knor, Guangjun Xu, Sanming Zhou:
  A study of 3-arc graphs. 344-353
• 
  Vadim E. Levit, David Tankus:
  Weighted well-covered graphs without C₄, C₅, C₆, C₇. 354-359
• 
  Paul D. Manuel:
  Minimum average congestion of enhanced and augmented hypercubes into complete binary trees. 360-366
• 
  Dara Moazzami:
  Tenacity of a graph with maximum connectivity. 367-380
• 
  Ján Plávka, Peter Szabó:
  On the λ-robustness of matrices over fuzzy algebra. 381-388
• 
  Dieter Rautenbach, Vinícius Fernandes dos Santos, Philipp Matthias Schäfer, Jayme Luiz Szwarcfiter:
  Characterization and representation problems for intersection betweennesses. 389-395

Note

• 
  Silvia M. Bianchi, Mariana S. Escalante, Graciela L. Nasini:
  On the behavior of the N₊-operator under blocker duality. 396-399

Volume 159, Number 6, March 2011

Special Section: Computational Molecular Biology

• 
  Julio Aracena, Eric Fanchon, Marco Montalva, Mathilde Noual:
  Combinatorics on update digraphs in Boolean networks. 401-409
• 
  Ruth Charney, Jacques Cohen, Aurélien Rizk:
  Efficient synthesis of a class of Boolean programs from I-O data: Application to genetic networks. 410-419

Contributions

• 
  Oded Berman, Dmitry Krass:
  On n-facility median problem with facilities subject to failure facing uniform demand. 420-432
• 
  Yago Diez, Joan Antoni Sellarès:
  Noisy colored point set matching. 433-449
• 
  Felix Distel, Baris Sertkaya:
  On the complexity of enumerating pseudo-intents. 450-466
• 
  Hong-Jian Lai, Yanting Liang:
  Supereulerian graphs in the graph family C₂(6, k). 467-477
• 
  Kun Meng, Chuang Lin, Wen An Liu, Yang Yang:
  Q-ary Rényi-Ulam pathological liar game with one lie. 478-483
• 
  Suk Jai Seo, Peter J. Slater:
  Open neighborhood locating-dominating in trees. 484-489

Note

• 
  Yiu Yu Ho, Ronald D. Dutton:
  Global secure sets of grid-like graphs. 490-496

Volume 159, Number 7, April 2011

• 
  Marina Lipshteyn, Ross M. McConnell, Haim Kaplan, Vadim E. Levit:
  Foreword. 497
• 
  Yuichi Asahiro, Eiji Miyano, Hirotaka Ono:
  Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree. 498-508
• 
  Andreas Brandstädt, Raffaele Mosca:
  On distance-3 matchings and induced matchings. 509-520
• 
  Domingos Moreira Cardoso, Nicholas Korpelainen, Vadim V. Lozin:
  On the complexity of the dominating induced matching problem in hereditary classes of graphs. 521-531
• 
  Márcia R. Cerioli, Fabiano de S. Oliveira, Jayme Luiz Szwarcfiter:
  On counting interval lengths of interval graphs. 532-543
• 
  Mirela Ben-Chen, Steven J. Gortler, Craig Gotsman, Camille Wormser:
  Distributed computation of virtual coordinates for greedy routing in sensor networks. 544-560
• 
  Celina M. H. de Figueiredo, Frédéric Maffray, Cláudia Villela Maciel:
  Transitive orientations in bull-reducible Berge graphs. 561-573
• 
  Arnaud Durand, Michel Habib:
  Complexity issues for the sandwich homogeneous set problem. 574-580
• 
  Elaine M. Eschen, Chính T. Hoàng, Jeremy P. Spinrad, R. Sritharan:
  On graphs without a C₄ or a diamond. 581-587
• 
  Danny Hermelin, Dror Rawitz:
  Optimization problems in multiple subtree graphs. 588-594
• 
  Robert E. Jamison:
  Orientable edge colorings of graphs. 595-604
• 
  Hal A. Kierstead, Karin Rebecca Saoub:
  First-Fit coloring of bounded tolerance graphs. 605-611
• 
  Jonathan Lenchner:
  On the affine Sylvester problem. 612-620
• 
  Min Chih Lin, Dieter Rautenbach, Francisco J. Soulignac, Jayme Luiz Szwarcfiter:
  Powers of cycles, powers of paths, and distance graphs. 621-627
• 
  Azaria Paz:
  A theory of decomposition into prime factors of layered interconnection networks. 628-646
• 
  Alan Shuchat, Randy Shull, Ann N. Trenk:
  Fractional weak discrepancy and split semiorders. 647-660
• 
  Rafael B. Teixeira, Simone Dantas, Celina M. H. de Figueiredo:
  The external constraint 4 nonempty part sandwich problem. 661-673

Volume 159, Number 8, April 2011

Special Section: Game Theory

• 
  Carlos Pereira dos Santos:
  Embedding processes in combinatorial game theory. 675-682
• 
  John Y. Kim:
  The incidence game chromatic number of paths and subgraphs of wheels. 683-694

Contributions

• 
  David Adjiashvili, Rico Zenklusen:
  An s-t connection problem with adaptability. 695-705
• 
  Behrooz Alizadeh, Rainer E. Burkard:
  Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees. 706-716
• 
  Jonathan Backer:
  Separator orders in interval, cocomparability, and AT-free graphs. 717-726
• 
  Bing Bai, Hongliang Lu, Qinglin Yu:
  Generalization of matching extensions in graphs (III). 727-732
• 
  Francine Blanchet-Sadri, John Lensmire:
  On minimal Sturmian partial words. 733-745
• 
  R. Chandrasekaran, Milind Dawande, Mehmet Baysan:
  On a labeling problem in graphs. 746-759
• 
  Gerard Jennhwa Chang, Jianfeng Hou, Nicolas Roussel:
  Local condition for planar graphs of maximum degree 7 to be 8-totally colorable. 760-768
• 
  Xue-Gang Chen, Moo Young Sohn:
  Bounds on the locating-total domination number of a tree. 769-773
• 
  Jun-Lin Guo, Tao-Ming Wang, Yue-Li Wang:
  Unique intersectability of diamond-free graphs. 774-778
• 
  Aleksandar Ilic, Dragan Stevanovic, Lihua Feng, Guihai Yu, Peter Dankelmann:
  Degree distance of unicyclic and bicyclic graphs. 779-788
• 
  Mihyun Kang, Oleg Pikhurko, Alexander Ravsky, Mathias Schacht, Oleg Verbitsky:
  Untangling planar graphs from a specified vertex position - Hard cases. 789-799
• 
  Qiuli Li, Saihua Liu, Heping Zhang:
  2-extendability and k-resonance of non-bipartite Klein-bottle polyhexes. 800-811
• 
  Ali Haydar Özer, Can C. Özturan:
  A direct barter model for course add/drop process. 812-825
• 
  Valery T. Stefanov, Stéphane Robin, Sophie Schbath:
  Occurrence of structured motifs in random sequences: Arbitrary number of boxes. 826-831
• 
  Lutz Volkmann:
  Upper bounds on the signed total domatic number of graphs. 832-837
• 
  Jinjiang Yuan, C. T. Ng, T. C. Edwin Cheng:
  Best semi-online algorithms for unbounded parallel batch scheduling. 838-847

Notes

• 
  R. Julian R. Abel, Ian Anderson, Norman J. Finizio:
  Necessary conditions for the existence of two classes of ZCPS-Wh(v). 848-851
• 
  Vesna Andova, Saso Bogoev, Darko Dimitrov, Marcin Pilipczuk, Riste Skrekovski:
  On the Zagreb index inequality of graphs with prescribed vertex degrees. 852-858
• 
  Adrian Dumitrescu, Minghui Jiang:
  Constrained k-center and movement to independence. 859-865
• 
  Mehdi Eliasi, Ali Iranmanesh:
  The hyper-Wiener index of the generalized hierarchical product of graphs. 866-871
• 
  Hermann Gruber:
  Bounding the feedback vertex number of digraphs in terms of vertex degrees. 872-875
• 
  Jianfeng Hou, Guizhen Liu, Guanghui Wang:
  Improved bounds for acyclic chromatic index of planar graphs. 876-881

Volume 159, Number 9, June 2011

• 
  Géraldine Heilporn, Jean-François Cordeau, Gilbert Laporte:
  An integer L-shaped algorithm for the Dial-a-Ride Problem with stochastic customer delays. 883-895
• 
  Evangelos Kranakis, Danny Krizanc, Euripides Markou:
  Deterministic symmetric rendezvous with tokens in a synchronous torus. 896-923
• 
  Yuanliang Zhang, Olga I. Kostyukova, Kil To Chong:
  A new time-discretization for delay multiple-input nonlinear systems using the Taylor method and first order hold. 924-938

Note

• 
  Henry Martyn Mulder, Beth Novick:
  An axiomatization of the median procedure on the n-cube. 939-944

Volume 159, Number 10, June 2011

• 
  Peter Dankelmann:
  On the distance distribution of trees. 945-952
• 
  Nicole Eggemann, Steven D. Noble:
  The clustering coefficient of a scale-free random graph. 953-965
• 
  Jochen Harant:
  A lower bound on independence in terms of degrees. 966-970
• 
  Hongbo Hua, Shenggui Zhang:
  Graphs with given number of cut vertices and extremal Merrifield-Simmons index. 971-980
• 
  Raphaël M. Jungers, Vincent D. Blondel:
  Observable graphs. 981-989
• 
  Léonard Kwuida, Stefan E. Schmidt:
  Valuations and closure operators on finite lattices. 990-1001
• 
  Yingjie Lan, Songqing Chen:
  Some special minimum k-geodetically connected graphs. 1002-1012
• 
  Anders Sune Pedersen, Dieter Rautenbach:
  Recolouring-resistant colourings. 1013-1021
• 
  Yann Strozecki:
  Monadic second-order model-checking on decomposable matroids. 1022-1039
• 
  Munevver Mine Subasi, Ersoy Subasi, Martin Anthony, Peter L. Hammer:
  A new imputation method for incomplete binary data. 1040-1047

Notes

• 
  Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. Henning:
  An extremal problem for total domination stable graphs upon edge removal. 1048-1052
• 
  Stephanie A. Rickett, Teresa W. Haynes:
  Total domination dot-stable graphs. 1053-1057

Erratum

• 
  Hande Yaman:
  Erratum to: Polyhedral analysis for the two-item uncapacitated lot-sizing problem with one-way substitution [Discrete Appl. Math. 157 (2009) 3133-3151]. 1058

Volume 159, Number 11, July 2011

Special Section: Computational Molecular Biology

• 
  David Canright, Sugata Gangopadhyay, Subhamoy Maitra, Pantelimon Stanica:
  Laced Boolean functions and subset sum problems in finite fields. 1059-1069
• 
  Ferdinando Cicalese, Travis Gagie, Eduardo Sany Laber, Martin Milanic:
  Competitive Boolean function evaluation: Beyond monotonicity, and the symmetric case. 1070-1078
• 
  Javier Herranz:
  Any 2-asummable bipartite function is weighted threshold. 1079-1084
• 
  Adrien Richard:
  Local negative circuits and fixed points in non-expansive Boolean networks. 1085-1093

Contributions

• 
  David Coudert, Jean-Sébastien Sereni:
  Characterization of graphs and digraphs with small process numbers. 1094-1109
• 
  E. Ebrahimi Targhi, Nader Jafari Rad, Lutz Volkmann:
  Unique response Roman domination in graphs. 1110-1117
• 
  Michael R. Fellows, Henning Fernau:
  Facility location problems: A parameterized view. 1118-1130
• 
  George B. Mertzios, Derek G. Corneil:
  Vertex splitting and the recognition of trapezoid graphs. 1131-1147
• 
  Stefko Miklavic, Martin Milanic:
  Equistable graphs, general partition graphs, triangle graphs, and graph products. 1148-1159

Notes

• 
  Pranav Anand, Henry Escuadro, Ralucca Gera, Craig H. Martell:
  Triangular line graphs and word sense disambiguation. 1160-1165
• 
  Nicola Apollonio, Massimiliano Caramia:
  Recognizing Helly Edge-Path-Tree graphs and their clique graphs. 1166-1175
• 
  Maurizio Monge:
  On perfect hashing of numbers with sparse digit representation via multiplication by a constant. 1176-1179
• 
  Dieter Rautenbach:
  Average distance and domination number revisited. 1180-1182
• 
  Huiyu Sheng, Yingqian Wang:
  A structural theorem for planar graphs with some applications. 1183-1187

Volume 159, Number 12, July 2011

• 
  Bostjan Bresar, Frantisek Kardos, Ján Katrenic, Gabriel Semanisin:
  Minimum k-path vertex cover. 1189-1195
• 
  Tiziana Calamoneri, Rossella Petreschi:
  The L(2, 1)-labeling of unigraphs. 1196-1206
• 
  Sergi Elizalde, Yangyang Liu:
  On basic forbidden patterns of functions. 1207-1216
• 
  Tomás Feder, Pavol Hell, David G. Schell, Juraj Stacho:
  Dichotomy for tree-structured trigraph list homomorphism problems. 1217-1224
• 
  Trevor J. Gionet Jr., Erika L. C. King, Yixiao Sha:
  A revision and extension of results on 4-regular, 4-connected, claw-free graphs. 1225-1230
• 
  Guanghui Wang, Shan Zhou, Guizhen Liu, Jianliang Wu:
  Circular vertex arboricity. 1231-1238
• 
  Weifan Wang, Qiaojun Shu, Kan Wang, Ping Wang:
  Acyclic chromatic indices of planar graphs with large girth. 1239-1253
• 
  Jinn-Shyong Yang, Hung-Chang Chan, Jou-Ming Chang:
  Broadcasting secure messages via optimal independent spanning trees in folded hypercubes. 1254-1263
• 
  Liron Yedidsion, Dvir Shabtay, Moshe Kaspi:
  Complexity analysis of an assignment problem with controllable assignment costs and its applications in scheduling. 1264-1278

Notes

• 
  Gustavo Bergantiños, Juan J. Vidal-Puga:
  The folk solution and Boruvka's algorithm in minimum cost spanning tree problems. 1279-1283
• 
  Bettina Klinz, Gerhard J. Woeginger:
  The Northwest corner rule revisited. 1284-1289
• 
  Ana Luzón, Manuel A. Morón:
  Self-inverse Sheffer sequences and Riordan involutions. 1290-1292
• 
  Gary MacGillivray, Jacobus Swarts:
  The C_k-extended graft construction. 1293-1301

Volume 159, Number 13, August 2011

• 
  Sergio Cabello, Marko Jakovac:
  On the b-chromatic number of regular graphs. 1303-1310
• 
  Sanjit Chatterjee, Alfred Menezes:
  On cryptographic protocols employing asymmetric pairings - The role of Ψ revisited. 1311-1322
• 
  Gholam Hossein Fath-Tabar, B. Vaez-Zadeh, Ali Reza Ashrafi, Ante Graovac:
  Some inequalities for the atom-bond connectivity index of graph operations. 1323-1330
• 
  Ramiro Feria-Purón, Mirka Miller, Guillermo Pineda-Villavicencio:
  On graphs of defect at most 2. 1331-1344
• 
  Takehiro Ito, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos:
  On disconnected cuts and separators. 1345-1351
• 
  Yury L. Orlovich, Alexandre Dolgui, Gerd Finke, Valery S. Gordon, Frank Werner:
  The complexity of dissociation set problems in graphs. 1352-1366
• 
  Edouard Wagneur, T. C. Edwin Cheng, C. T. Daniel Ng:
  A closed-form solution for the optimal release times for the F2 deteriorating jobs ∑w_jC_j problem. 1367-1376

Note

• 
  Kristina C. Garrett, Charles McEachern, Todd Frederick, Olaf A. Hall-Holt:
  Fast computation of Andrews' smallest part statistic and conjectured congruences. 1377-1380

Volume 159, Number 14, August 2011

• 
  Eva Belmont:
  A complete characterization of paths that are m-step competition graphs. 1381-1390
• 
  Shinya Fujita, Colton Magnant:
  Properly colored paths and cycles. 1391-1397
• 
  Petros Hadjicostas, K. B. Lakshmanan:
  Recursive merge sort with erroneous comparisons. 1398-1417
• 
  Ali Nourollah, Mohammadreza Razzazi:
  Minimum cost open chain reconfiguration. 1418-1424
• 
  Shiying Wang, Yuxing Yang, Jing Li, Shangwei Lin:
  Hamiltonian cycles passing through linear forests in k-ary n-cubes. 1425-1435

Notes

• 
  Adrian Dumitrescu, Minghui Jiang:
  Sweeping an oval to a vanishing point. 1436-1442
• 
  Michael A. Henning, Nader Jafari Rad, Joanna Raczek:
  A note on total reinforcement in graphs. 1443-1446
• 
  Hong-Jian Lai, Yanting Liang, Ping Li, Jinquan Xu:
  Degree sequences and graphs with disjoint spanning trees. 1447-1452
• 
  Vincent Vajnovszki:
  A new Euler-Mahonian constructive bijection. 1453-1459

Volume 159, Number 15, September 2011

Special Section: Game Theory

• 
  Endre Boros, Vladimir Gurvich, Kazuhisa Makino, Wei Shao:
  Nash-solvable two-person symmetric cycle game forms. 1461-1487
• 
  Klaus Nehring, Marcus Pivato:
  Incoherent majorities: The McGarvey problem in judgement aggregation. 1488-1507
• 
  Michal Penn, Maria Polukarov, Moshe Tennenholtz:
  Congestion games with failures. 1508-1525
• 
  Alexander Shapovalov:
  Occupation games on graphs in which the second player takes almost all vertices. 1526-1527

Contributions

• 
  Gunnar Brinkmann, Nicolas Van Cleemput:
  Classification and generation of nanocones. 1528-1539
• 
  Chunxia Chen, Changhong Lu, Zhengke Miao:
  Identifying codes and locating-dominating sets on paths and cycles. 1540-1547
• 
  Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. Henning:
  Total domination changing and stable graphs upon vertex removal. 1548-1554
• 
  Bin Fu, Yumei Huo, Hairong Zhao:
  Approximation schemes for parallel machine scheduling with availability constraints. 1555-1565
• 
  Marja Hassinen, Joel Kaasinen, Evangelos Kranakis, Valentin Polishchuk, Jukka Suomela, Andreas Wiese:
  Analysing local algorithms in location-aware quasi-unit-disk graphs. 1566-1580
• 
  Xiaoyan Jiang, Heping Zhang:
  On forcing matching number of boron-nitrogen fullerene graphs. 1581-1593
• 
  Daobin Li, Baoyindureng Wu, Xunuan Yang, Xinhui An:
  Nordhaus-Gaddum-type theorem for Wiener index of graphs when decomposing into three parts. 1594-1600
• 
  Shuhua Li, Guoping Wang:
  Vertex PI indices of four sums of graphs. 1601-1607
• 
  Konrad Schwarz, Arne Dür:
  Visualization of quasi-median networks. 1608-1616
• 
  Rundan Xing, Bo Zhou, Fengming Dong:
  On atom-bond connectivity index of connected graphs. 1617-1630
• 
  Kexiang Xu, Kinkar Chandra Das:
  On Harary index of graphs. 1631-1640

Notes

• 
  Phillip E. C. Compeau:
  Girth of pancake graphs. 1641-1645
• 
  Serkan Eryilmaz:
  On the lifetime of a random binary sequence. 1646-1649
• 
  Hervé Hocquard, Petru Valicov:
  Strong edge colouring of subcubic graphs. 1650-1657

Volume 159, Number 16, September 2011

• 
  Sonia Cafieri, Ulrich Faigle, Leo Liberti:
  8th Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009). 1659
• 
  Stephan Dominique Andres, Winfried Hochstättler, Christiane Schallück:
  The game chromatic index of wheels. 1660-1665
• 
  David Auger, Irène Charon, Olivier Hudry, Antoine Lobstein:
  On the sizes of graphs and their powers: The undirected case. 1666-1675
• 
  Rafael Ayala, Desamparados Fernández-Ternero, José Antonio Vilches:
  The number of excellent discrete Morse functions on graphs. 1676-1688
• 
  Walid Ben-Ameur, José Neto:
  A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems. 1689-1698
• 
  Flavia Bonomo, Guillermo Durán, Luciano N. Grippo, Martín Darío Safe:
  Partial characterizations of circle graphs. 1699-1706
• 
  Guillaume Collet, Rumen Andonov, Nicola Yanev, Jean-François Gibrat:
  Local protein threading by Mixed Integer Programming. 1707-1716
• 
  Simone Dantas, Celina M. H. de Figueiredo, Murilo Vicente Gonçalves da Silva, Rafael B. Teixeira:
  On the forbidden induced subgraph sandwich problem. 1717-1725
• 
  Andreas Darmann, Ulrich Pferschy, Joachim Schauer, Gerhard J. Woeginger:
  Paths, trees and matchings under disjunctive constraints. 1726-1735
• 
  Ulrich Faigle, Jan Voss:
  A system-theoretic model for cooperation, interaction and allocation. 1736-1750
• 
  Tobias Friedrich, Nils Hebbinghaus:
  Average update times for fully-dynamic all-pairs shortest paths. 1751-1758
• 
  Valery S. Gordon, Yury L. Orlovich, Chris N. Potts, Vitaly A. Strusevich:
  Hamiltonian properties of locally connected graphs with bounded vertex degree. 1759-1774
• 
  André Luiz Pires Guedes, Lilian Markenzon, Luérbio Faria:
  Flow hypergraph reducibility. 1775-1785
• 
  Illés Horváth, Gyula Y. Katona:
  Extremal P₄-stable graphs. 1786-1792
• 
  Bo Jiang, Xuehou Tan:
  Searching for mobile intruders in circular corridors by two 1-searchers. 1793-1805
• 
  Ross J. Kang, Tobias Müller:
  Frugal, acyclic and star colourings of graphs. 1806-1814
• 
  Etienne de Klerk, Cristian Dobre:
  A comparison of lower bounds for the symmetric circulant traveling salesman problem. 1815-1826
• 
  Stefanie Kosuch, Abdel Lisser:
  On two-stage stochastic knapsack problems. 1827-1841
• 
  Andrew Lyons:
  Acyclic and star colorings of cographs. 1842-1850
• 
  Raphael C. S. Machado, Celina M. H. de Figueiredo:
  Total chromatic number of unichord-free graphs. 1851-1864
• 
  Gaia Nicosia, Andrea Pacifici, Ulrich Pferschy:
  Competitive subset selection with two agents. 1865-1877
• 
  B. S. Panda, Preeti Goel:
  L(2, 1)-labeling of perfect elimination bipartite graphs. 1878-1888
• 
  Petros A. Petrosyan, H. E. Sargsyan:
  On resistance of graphs. 1889-1900
• 
  Luidi Simonetti, Yuri Frota, Cid C. de Souza:
  The ring-star problem: A new integer programming formulation and a branch-and-cut algorithm. 1901-1914

Volume 159, Number 17, October 2011

Contributions

• 
  Peter R. J. Asveld:
  Permuting operations on strings and their relation to prime numbers. 1915-1932
• 
  Cristina Bazgan, Sonia Toubaline, Zsolt Tuza:
  The most vital nodes with respect to independent set and vertex cover. 1933-1946
• 
  Oleg V. Borodin, Anna O. Ivanova, Mickaël Montassier, André Raspaud:
  (k, j)-coloring of sparse graphs. 1947-1953
• 
  Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos:
  Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. 1954-1970
• 
  Maria Chudnovsky, Bernard Ries, Yori Zwols:
  Claw-free graphs with strongly perfect complements. Fractional and integral version. Part I. Basic graphs. 1971-1995
• 
  Maria Chudnovsky, Bernard Ries, Yori Zwols:
  Claw-free graphs with strongly perfect complements. Fractional and integral version, Part II: Nontrivial strip-structures. 1996-2029
• 
  Kinkar Chandra Das, Ivan Gutman, Boris Furtula:
  On the first geometric-arithmetic index of graphs. 2030-2037
• 
  Jianrong Dong, David Fernández-Baca, Fred R. McMorris, Robert C. Powers:
  An axiomatic study of Majority-rule (+ ) and associated consensus functions on hierarchies. 2038-2044
• 
  Francesca Fiorenzi, Pascal Ochem, Patrice Ossona de Mendez, Xuding Zhu:
  Thue choosability of trees. 2045-2049
• 
  Xing Gao, Yanfeng Luo, Wenwen Liu:
  Resistance distances and the Kirchhoff index in Cayley graphs. 2050-2057
• 
  Tatjana Gerzen:
  On a group testing problem: Characterization of graphs with 2-complexity c₂ and maximum number of edges. 2058-2068
• 
  Jingjing Jin:
  Some properties for a class of interchange graphs. 2069-2077
• 
  Ernst J. Joubert:
  Total restrained domination in claw-free graphs with minimum degree at least two. 2078-2097
• 
  Sergey Kitaev, Jeffrey B. Remmel:
  Enumerating (2+2)-free posets by the number of minimal elements and other statistics. 2098-2108
• 
  Paul D. Manuel, Micheal Arockiaraj, Indra Rajasingh, Bharati Rajan:
  Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength. 2109-2116
• 
  Nathan Pflueger:
  Graph reductions, binary rank, and pivots in gene assembly. 2117-2134
• 
  Won-Min Song, Tiziana di Matteo, Tomaso Aste:
  Nested hierarchies in planar graphs. 2135-2146
• 
  Johan M. M. van Rooij, Hans L. Bodlaender:
  Exact algorithms for dominating set. 2147-2164

Notes

• 
  Birk Eisermann:
  A sufficient condition for boundedness of tolerance graphs. 2165-2169
• 
  Ankit Garg, Arpit Goel, Amitabha Tripathi:
  Constructive extensions of two results on graphic sequences. 2170-2174
• 
  Yoshifumi Sakai:
  A fast algorithm for multiplying min-sum permutations. 2175-2183
• 
  Ignasi Sau, Dimitrios M. Thilikos:
  On self-duality of branchwidth in graphs of bounded genus. 2184-2186

Communication

• 
  Frauke Liers, G. Pardella:
  Simplifying maximum flow computations: The effect of shrinking and good initial flows. 2187-2203

Volume 159, Number 18, December 2011

Contributions

• 
  Hee-Kap Ahn, Sang Won Bae, Marc J. van Kreveld, Iris Reinbacher, Bettina Speckmann:
  Empty pseudo-triangles in point sets. 2205-2213
• 
  Ali Behtoei, Behnaz Omoomi:
  On the locating chromatic number of Kneser graphs. 2214-2221
• 
  Jon-Lark Kim, Seog-Jin Kim:
  The 2-distance coloring of the Cartesian product of cycles using optimal Lee codes. 2222-2228
• 
  Jacques-Olivier Lachaud, Xavier Provençal:
  Two linear-time algorithms for computing the minimum length polygon of a digital contour. 2229-2250
• 
  Chungmok Lee, Sungsoo Park:
  Chebyshev center based column generation. 2251-2265

Notes

• 
  Ting Chen:
  A revised algorithm for searching for all defective edges in a graph. 2266-2268
• 
  Ali Kakhbod, Morteza Zadimoghaddam:
  On the construction of prefix-free and fix-free codes with specified codeword compositions. 2269-2275
• 
  Steven D. Noble, Pierre Hansen, Nenad Mladenovic:
  Maximizing edge-ratio is NP-complete. 2276-2280
• 
  María Soto, André Rossi, Marc Sevaux:
  Three new upper bounds on the chromatic number. 2281-2289
• 
  Ernest X. W. Xia, X. M. Yao:
  The signs of three-term recurrence sequences. 2290-2296