Discrete Applied Mathematics, Volume 160

Volume 160, Numbers 1-2, January 2012

Contributions

• 
  Hosam Abdo, Darko Dimitrov, Ivan Gutman:
  On the Zagreb indices equality. 1-8
• 
  Rangaswami Balakrishnan, T. Kavaskar:
  b-coloring of Kneser graphs. 9-14
• 
  Adrien Bellanger, Adam Janiak, Mikhail Y. Kovalyov, Ammar Oulamara:
  Scheduling an unbounded batching machine with job processing time compatibilities. 15-23
• 
  Enrique Bendito, Ángeles Carmona, Andrés M. Encinas:
  The Kirchhoff indices of join networks. 24-37
• 
  Daniel K. Benvenuti, Abraham P. Punnen:
  Three value TSP and linkages with the three value linear spanning 2-forests. 38-52
• 
  Nadja Betzler, Robert Bredereck, Rolf Niedermeier, Johannes Uhlmann:
  On Bounded-Degree Vertex Deletion parameterized by treewidth. 53-60
• 
  Yacine Boufkhad, Thomas Hugel:
  Estimating satisfiability. 61-80
• 
  Hadrien Cambazard, Eoin O'Mahony, Barry O'Sullivan:
  A shortest path-based approach to the multileaf collimator sequencing problem. 81-99
• 
  Yeow Meng Chee, Lijun Ji, Andrew Lim, Anthony K. H. Tung:
  Arboricity: An acyclic hypergraph decomposition problem motivated by database theory. 100-107
• 
  Gong Chen, Zhongxun Zhu:
  The number of independent sets of unicyclic graphs with given matching number. 108-115
• 
  Amir Daneshgar, Ramin Javadi:
  On the complexity of isoperimetric problems on trees. 116-131
• 
  Emilio Di Giacomo, Walter Didimo, Peter Eades, Seok-Hee Hong, Giuseppe Liotta:
  Bounds on the crossing resolution of complete geometric graphs. 132-139
• 
  Ramiro Feria-Purón, Guillermo Pineda-Villavicencio:
  On bipartite graphs of defect at most 4. 140-154
• 
  Petr A. Golovach, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos:
  Containment relations in split graphs. 155-163
• 
  Michael A. Henning, Adel P. Kazemi:
  Total domination in inflated graphs. 164-169
• 
  Hongbo Hua, Shenggui Zhang, Kexiang Xu:
  Further results on the eccentric distance sum. 170-180

Notes

• 
  Bojan Basic:
  Counter-intuitive answers to some questions concerning minimal-palindromic extensions of binary words. 181-186
• 
  Yun Ding, Rosena R. X. Du:
  Counting humps in Motzkin paths. 187-191
• 
  Stefano Gualandi, Federico Malucelli:
  A simple branching scheme for vertex coloring problems. 192-196

Volume 160, Number 3, February 2012

Contributions

• 
  Qiaoming Han, Abraham P. Punnen:
  Strong and weak edges of a graph and linkages with the vertex cover problem. 197-203
• 
  Aleksandar Ilic, Bo Zhou:
  On reformulated Zagreb indices. 204-209
• 
  Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri, Asghar Asgharian-Sardroud:
  A linear-time algorithm for the longest path problem in rectangular grid graphs. 210-217
• 
  (Withdrawn) Pancyclic graphs and degree sum and neighborhood union involving distance two. 218-223
• 
  Chandra Mohan Krishnamurthy, R. Sritharan:
  Maximum induced matching problem on hhd-free graphs. 224-230
• 
  Jing Li, Di Liu, Jun Yuan:
  Pancyclicity of k-ary n-cube networks with faulty vertices and edges. 231-238
• 
  Wu-Hsiung Lin, Gerard J. Chang:
  Equitable colorings of Cartesian products of graphs. 239-247
• 
  M. J. Morgan, Simon Mukwembi, Henda C. Swart:
  A lower bound on the eccentric connectivity index of a graph. 248-258
• 
  Carmen Ortiz, Mónica Villanueva:
  Maximal independent sets in caterpillar graphs. 259-266
• 
  K. Pattabiraman, P. Paulraja:
  On some topological indices of the tensor products of graphs. 267-279
• 
  Ricardo Riaza:
  Cyclic matrices of weighted digraphs. 280-290
• 
  Sheng-Yi Cai, Qi-Fan Yang:
  Online scheduling on three uniform machines. 291-302
• 
  Zhanjun Su, Sipeng Li, Jian Shen, Liping Yuan:
  On the relative distances of nine or ten points in the boundary of a plane convex body. 303-305
• 
  Zhou Xu, Dongsheng Xu, Wenbin Zhu:
  Approximation results for a min-max location-routing problem. 306-320
• 
  Kexiang Xu:
  Trees with the seven smallest and eight greatest Harary indices. 321-331
• 
  Li Zhang:
  A (3, 1)*-choosable theorem on toroidal graphs. 332-338

Notes

• 
  Michal Przykucki:
  Optimal stopping in a search for a vertex with full degree in a random graph. 339-343
• 
  Stefan Stanimirovic, Predrag S. Stanimirovic, Aleksandar Ilic:
  Ballot matrix as Catalan matrix power and related identities. 344-351
• 
  Jian-Hua Yin:
  A short constructive proof of A. R. Rao's characterization of potentially K_r+1-graphic sequences. 352-354

Volume 160, Numbers 4-5, March 2012

Special Section: Boolean and Pseudo-Boolean Functions

• 
  Martin Anthony, Joel Ratsaby:
  Robust cutpoints in the logical analysis of numerical data. 355-364
• 
  Ondrej Cepek, Petr Kucera, Petr Savický:
  Boolean functions with a simple certificate for CNF complexity. 365-382
• 
  Miguel Couceiro, Erkko Lehtonen, Tamás Waldhauser:
  The arity gap of order-preserving functions and extensions of pseudo-Boolean functions. 383-390
• 
  Thomas W. Cusick, Daniel Padgett:
  A recursive formula for weights of Boolean rotation symmetric functions. 391-397
• 
  Jacques Demongeot, Mathilde Noual, Sylvain Sené:
  Combinatorics of Boolean automata circuits dynamics. 398-415
• 
  Vladimir Kolmogorov:
  Generalized roof duality and bisubmodular functions. 416-426
• 
  Ziran Tu, Yingpu Deng:
  Boolean functions optimizing most of the cryptographic criteria. 427-435

Contributions

• 
  Sarah Spence Adams, Paul Booth, Harold Jaffe, Denise Sakai Troxell, S. Luke Zinnen:
  Exact lambda-numbers of generalized Petersen graphs of certain higher-orders and on Möbius strips. 436-447
• 
  Milica Andelic, Carlos M. da Fonseca, Slobodan K. Simic, Dejan V. Tosic:
  Connected graphs of fixed order and size with maximal Q-index: Some spectral bounds. 448-459
• 
  Drago Bokal, Bostjan Bresar, Janja Jerebic:
  A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks. 460-470
• 
  Andreas Brandstädt, Vassilis Giakoumakis, Frédéric Maffray:
  Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences. 471-478
• 
  Chan-Wei Chang, Ma-Lian Chia, Cheng-Ju Hsu, David Kuo, Li-Ling Lai, Fu-Hsing Wang:
  Global defensive alliances of trees and Cartesian product of paths and cycles. 479-487
• 
  Xue-Gang Chen, Shinya Fujita, Michitaka Furuya, Moo Young Sohn:
  Constructing connected bicritical graphs with edge-connectivity 2. 488-493
• 
  Marek Cygan, Marcin Pilipczuk:
  Bandwidth and distortion revisited. 494-504
• 
  Július Czap, Dávid Hudák:
  1-planarity of complete multipartite graphs. 505-512
• 
  Nicole Eggemann, Steven D. Noble:
  The complexity of two graph orientation problems. 513-517
• 
  Jan Ekstein, Premysl Holub, Bernard Lidický:
  Packing chromatic number of distance graphs. 518-524
• 
  Ben Emanuel, Shmuel Wimer, Gershon Wolansky:
  Using well-solvable quadratic assignment problems for VLSI interconnect applications. 525-535
• 
  Chiara Epifanio, Christiane Frougny, Alessandra Gabriele, Filippo Mignosi, Jeffrey O. Shallit:
  Sturmian graphs and integer representations over numeration systems. 536-547
• 
  Jywe-Fei Fang, Chien-Hung Huang:
  Geodesic pancyclicity and balanced pancyclicity of the generalized base-b hypercube. 548-559
• 
  Xing Gao, Yanfeng Luo, Wenwen Liu:
  Kirchhoff index in line, subdivision and total graphs of a regular graph. 560-565
• 
  Yong Gao:
  Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs. 566-578
• 
  Yanmei Hong, Jixiang Meng, Zhao Zhang:
  Edge fault tolerance of graphs with respect to super edge connectivity. 579-587
• 
  Takuya Iimura, Kazuo Murota, Akihisa Tamura:
  Sperner's lemma and zero point theorems on a discrete simplex and a discrete simplotope. 588-592
• 
  Arnold Knopfmacher, Toufik Mansour:
  Record statistics in a random composition. 593-603
• 
  Daniel Lemire:
  The universality of iterated hashing over variable-length strings. 604-617
• 
  Kun Meng, Chuang Lin, Wen An Liu, Yang Yang, Gyula O. H. Katona:
  Minimum average-case queries of q+1-ary search game with small sets. 618-627
• 
  Pedro Miranda, Michel Grabisch:
  An algorithm for finding the vertices of the k-additive monotone core. 628-639
• 
  Ján Plávka:
  On the O(n³) algorithm for checking the strong robustness of interval fuzzy matrices. 640-647
• 
  T. Schiffer, Franz Aurenhammer, M. Demuth:
  Computing convex quadrangulations. 648-656
• 
  Lanzhen Song, William Staton, Bing Wei:
  Independence polynomials of some compound graphs. 657-663
• 
  Yingqian Wang, Qian Wu:
  Linear coloring of sparse graphs. 664-672

Notes

• 
  Stephen Bowser, Charles Cable:
  At least three minimal quasi-kernels. 673-675
• 
  Mustapha Chellali, Nader Jafari Rad, Abdollah Khodkar:
  On 3-y_t-vertex critical graphs of diameter three. 676-681

Volume 160, Number 6, April 2012

• 
  Pinar Heggernes, Jan Kratochvíl, Andrzej Proskurowski:
  Guest editors' foreword. 683-684

Graph Classes

• 
  Ferdinando Cicalese, Martin Milanic:
  Graphs of separability at most 2. 685-696
• 
  Tomás Feder, Pavol Hell, Jing Huang, Arash Rafiey:
  Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms. 697-707
• 
  Emeric Gioan, Christophe Paul:
  Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs. 708-733
• 
  Petr A. Golovach, Pinar Heggernes, Rodica Mihai:
  Edge search number of cographs. 734-743
• 
  Daniel Gonçalves, Frédéric Havet, Alexandre Pinlou, Stéphan Thomassé:
  On spanning galaxies in digraphs. 744-754

Optimization

• 
  Karina Chudá, Martin Skoviera:
  L(2, 1)-labelling of generalized prisms. 755-763
• 
  Jirí Fiala, Petr A. Golovach, Jan Kratochvíl, Bernard Lidický, Daniël Paulusma:
  Distance three labelings of trees. 764-779
• 
  Petr A. Golovach, Jan Kratochvíl, Ondrej Suchý:
  Parameterized complexity of generalized domination problems. 780-792
• 
  Torben Hagerup:
  A strengthened analysis of an algorithm for Dominating Set in planar graphs. 793-798
• 
  Pim van 't Hof, Marcin Kaminski, Daniël Paulusma, Stefan Szeider, Dimitrios M. Thilikos:
  On graph contractions and induced minors. 799-809
• 
  Frank Kammer, Torsten Tholey:
  The complexity of minimum convex coloring. 810-833

Width Parameters

• 
  Derek G. Corneil, Michel Habib, Jean-Marc Lanlignel, Bruce A. Reed, Udi Rotics:
  Polynomial-time recognition of clique-width ≤3 graphs. 834-865
• 
  Bruno Courcelle:
  On the model-checking of monadic second-order formulas with edge set quantifications. 866-887
• 
  Pinar Heggernes, Daniel Meister, Charis Papadopoulos:
  Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs. 888-901
• 
  David Knipe:
  Trimming weighted graphs of bounded treewidth. 902-912
• 
  Daniel Král':
  Decomposition width of matroids. 913-923

Volume 160, Numbers 7-8, May 2012

Special Section: Game Theory

• 
  Sylvain Béal, Eric Rémila, Philippe Solal:
  On the number of blocks required to access the core. 925-932
• 
  Vladimir I. Danilov, Alexander V. Karzanov, Gleb A. Koshevoy:
  Condorcet domains of tiling type. 933-940
• 
  Vladimir Gurvich:
  Further generalizations of the Wythoff game and the minimum excludant. 941-947
• 
  Nikolai S. Kukushkin:
  Cournot tâtonnement and dominance solvability in finite games. 948-958
• 
  Kitty Meeks, Alexander Scott:
  The complexity of flood-filling games on graphs. 959-969
• 
  Justo Puerto, Arie Tamir, Federico Perea:
  Cooperative location games based on the minimum diameter spanning Steiner subgraph problem. 970-979
• 
  Shao Huang, Chao Wang:
  Recursive method to solve the problem of "Gambling with God". 980-984

Contributions

• 
  Robert E. L. Aldred, Michael D. Plummer:
  Proximity thresholds for matching extension in the torus and Klein bottle. 985-991
• 
  Abbas Alhakim:
  Spans of preference functions for de Bruijn sequences. 992-998
• 
  Rémy Belmonte, Pinar Heggernes, Pim van 't Hof:
  Edge contractions in subclasses of chordal graphs. 999-1010
• 
  Alexandre Blondin Massé, Srecko Brlek, Sébastien Labbé:
  A parallelogram tile fills the plane by translation in at most two distinct ways. 1011-1018
• 
  Marianna Bolla, Tamás Kói, András Krámli:
  Testability of minimum balanced multiway cut densities. 1019-1027
• 
  Marcus Brazil, Charl J. Ras, Doreen A. Thomas:
  The bottleneck 2-connected k-Steiner network problem for k≤2. 1028-1038
• 
  Valentin E. Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni:
  Approximation algorithms for a geometric set cover problem. 1039-1052
• 
  Yair Caro, Michael A. Henning:
  Directed domination in oriented graphs. 1053-1063
• 
  Ye Chen, Suohai Fan, Hong-Jian Lai, Huimin Song, Lei Sun:
  On dynamic coloring for planar graphs and graphs of higher genus. 1064-1071
• 
  Marc Demange, Gabriele Di Stefano, Benjamin Leroy-Beaulieu:
  On the online track assignment problem. 1072-1093
• 
  Christoph Dürr, Maurice Queyranne, Frits C. R. Spieksma, Fabrice Talla Nobibon, Gerhard J. Woeginger:
  The interval ordering problem. 1094-1103
• 
  Shinya Fujita, Michitaka Furuya, Colton Magnant:
  k-Rainbow domatic numbers. 1104-1113
• 
  Ian D. Gray, Jim A. MacDougall:
  Vertex-magic labeling of regular graphs: Disjoint unions and assemblages. 1114-1125
• 
  Brian Heinold:
  The sum choice number of P₃ P_n. 1126-1136
• 
  Michael A. Henning, Ernst J. Joubert, Justin Southey:
  Multiple factor Nordhaus-Gaddum type results for domination and total domination. 1137-1142
• 
  Michael A. Henning, Nader Jafari Rad:
  On α-total domination in graphs. 1143-1151
• 
  Hongbo Hua, Shenggui Zhang:
  On the reciprocal degree distance of graphs. 1152-1163
• 
  Fethi Jarray, Christophe Picouleau:
  Minimum decomposition into convex binary matrices. 1164-1175
• 
  Suh-Ryung Kim, Boram Park, Yoshio Sano:
  The competition numbers of complete multipartite graphs with many partite sets. 1176-1182
• 
  William Klostermeyer, Christina M. Mynhardt:
  Vertex covers and eternal dominating sets. 1183-1190
• 
  Ji Tian, T. C. E. Cheng, C. T. Ng, Jinjiang Yuan:
  An improved on-line algorithm for single parallel-batch machine scheduling with delivery times. 1191-1210
• 
  Qiaojun Shu, Weifan Wang, Yiqiao Wang:
  Acyclic edge coloring of planar graphs without 5-cycles. 1211-1223
• 
  Ge Xia, Yong Zhang:
  Kernelization for cycle transversal problems. 1224-1231
• 
  Weigen Yan, Yeong-Nan Yeh, Fuji Zhang:
  The asymptotic behavior of some indices of iterated line graphs of regular graphs. 1232-1239
• 
  Peng Zhang, Daming Zhu, Junfeng Luan:
  An approximation algorithm for the Generalized k-Multicut problem. 1240-1247
• 
  Jin-Xin Zhou:
  Super restricted edge connectivity of regular edge-transitive graphs. 1248-1252

Notes

• 
  Maddalena Cavicchioli:
  Acute triangulations of convex quadrilaterals. 1253-1256
• 
  Wei Dong:
  A note on entire choosability of plane graphs. 1257-1261
• 
  Alexander Grigoriev, Bert Marchal, Natalya Usotskaya, Ioan Todinca:
  A note on planar graphs with large width parameters and small grid-minors. 1262-1269
• 
  Stefan Gyürki:
  On the difference of the domination number of a digraph and of its reverse. 1270-1276
• 
  Sandi Klavzar, Khaled Salem:
  A characterization of 1-cycle resonant graphs among bipartite 2-connected plane graphs. 1277-1280
• 
  Oliver Schaudt:
  On graphs for which the connected domination number is at most the total domination number. 1281-1284
•