An Eulerian walk (or Eulerian trail) is a walk (resp. trail) that visits every edge of a graph
 NSFPAR ID:
 10284040
 Date Published:
 Journal Name:
 International Journal of Computational Geometry & Applications
 ISSN:
 02181959
 Page Range / eLocation ID:
 1 to 29
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract G at least (resp. exactly) once. This notion was first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. But what if Euler had to take a bus? In a temporal graph , with$$\varvec{(G,\lambda )}$$ $(G,\lambda )$ , an edge$$\varvec{\lambda : E(G)}\varvec{\rightarrow } \varvec{2}^{\varvec{[\tau ]}}$$ $\lambda :E\left(G\right)\to {2}^{\left[\tau \right]}$ is available only at the times specified by$$\varvec{e}\varvec{\in } \varvec{E(G)}$$ $e\in E\left(G\right)$ , in the same way the connections of the public transportation network of a city or of sightseeing tours are available only at scheduled times. In this paper, we deal with temporal walks, local trails, and trails, respectively referring to edge traversal with no constraints, constrained to not repeating the same edge in a single timestamp, and constrained to never repeating the same edge throughout the entire traversal. We show that, if the edges are always available, then deciding whether$$\varvec{\lambda (e)}\varvec{\subseteq } \varvec{[\tau ]}$$ $\lambda \left(e\right)\subseteq \left[\tau \right]$ has a temporal walk or trail is polynomial, while deciding whether it has a local trail is$$\varvec{(G,\lambda )}$$ $(G,\lambda )$ complete even if$$\varvec{\texttt {NP}}$$ $\mathrm{NP}$ . In contrast, in the general case, solving any of these problems is$$\varvec{\tau = 2}$$ $\tau =2$ complete, even under very strict hypotheses. We finally give$$\varvec{\texttt {NP}}$$ $\mathrm{NP}$ algorithms parametrized by$$\varvec{\texttt {XP}}$$ $\mathrm{XP}$ for walks, and by$$\varvec{\tau }$$ $\tau $ for trails and local trails, where$$\varvec{\tau +tw(G)}$$ $\tau +tw\left(G\right)$ refers to the treewidth of$$\varvec{tw(G)}$$ $tw\left(G\right)$ .$$\varvec{G}$$ $G$ 
Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let G be a connected boundeddegree graph. Given an edge e in G we would like to decide whether e belongs to a connected subgraph math formula consisting of math formula edges (for a prespecified constant math formula), where the decision for different edges should be consistent with the same subgraph math formula. Can this task be performed by inspecting only a constant number of edges in G? Our main results are: We show that if every tvertex subgraph of G has expansion math formula then one can (deterministically) construct a sparse spanning subgraph math formula of G using few inspections. To this end we analyze a “local” version of a famous minimumweight spanning tree algorithm. We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of 3regular graphs of high girth, in which every tvertex subgraph has expansion math formula. We prove that for this family of graphs, any local algorithm for the sparse spanning graph problem requires inspecting a number of edges which is proportional to the girth.more » « less

This data set for the manuscript entitled "Design of Peptides that Fold and SelfAssemble on Graphite" includes all files needed to run and analyze the simulations described in the this manuscript in the molecular dynamics software NAMD, as well as the output of the simulations. The files are organized into directories corresponding to the figures of the main text and supporting information. They include molecular model structure files (NAMD psf or Amber prmtop format), force field parameter files (in CHARMM format), initial atomic coordinates (pdb format), NAMD configuration files, Colvars configuration files, NAMD log files, and NAMD output including restart files (in binary NAMD format) and trajectories in dcd format (downsampled to 10 ns per frame). Analysis is controlled by shell scripts (Bashcompatible) that call VMD Tcl scripts or python scripts. These scripts and their output are also included.
Version: 2.0
Changes versus version 1.0 are the addition of the free energy of folding, adsorption, and pairing calculations (Sim_Figure7) and shifting of the figure numbers to accommodate this addition.
Conventions Used in These Files
===============================Structure Files

 graph_*.psf or sol_*.psf (original NAMD (XPLOR?) format psf file including atom details (type, charge, mass), as well as definitions of bonds, angles, dihedrals, and impropers for each dipeptide.) graph_*.pdb or sol_*.pdb (initial coordinates before equilibration)
 repart_*.psf (same as the above psf files, but the masses of nonwater hydrogen atoms have been repartitioned by VMD script repartitionMass.tcl)
 freeTop_*.pdb (same as the above pdb files, but the carbons of the lower graphene layer have been placed at a single z value and marked for restraints in NAMD)
 amber_*.prmtop (combined topology and parameter files for Amber force field simulations)
 repart_amber_*.prmtop (same as the above prmtop files, but the masses of nonwater hydrogen atoms have been repartitioned by ParmEd)Force Field Parameters

CHARMM format parameter files:
 par_all36m_prot.prm (CHARMM36m FF for proteins)
 par_all36_cgenff_no_nbfix.prm (CGenFF v4.4 for graphene) The NBFIX parameters are commented out since they are only needed for aromatic halogens and we use only the CG2R61 type for graphene.
 toppar_water_ions_prot_cgenff.str (CHARMM water and ions with NBFIX parameters needed for protein and CGenFF included and others commented out)Template NAMD Configuration Files

These contain the most commonly used simulation parameters. They are called by the other NAMD configuration files (which are in the namd/ subdirectory):
 template_min.namd (minimization)
 template_eq.namd (NPT equilibration with lower graphene fixed)
 template_abf.namd (for adaptive biasing force)Minimization

 namd/min_*.0.namdEquilibration

 namd/eq_*.0.namdAdaptive biasing force calculations

 namd/eabfZRest7_graph_chp1404.0.namd
 namd/eabfZRest7_graph_chp1404.1.namd (continuation of eabfZRest7_graph_chp1404.0.namd)Log Files

For each NAMD configuration file given in the last two sections, there is a log file with the same prefix, which gives the text output of NAMD. For instance, the output of namd/eabfZRest7_graph_chp1404.0.namd is eabfZRest7_graph_chp1404.0.log.Simulation Output

The simulation output files (which match the names of the NAMD configuration files) are in the output/ directory. Files with the extensions .coor, .vel, and .xsc are coordinates in NAMD binary format, velocities in NAMD binary format, and extended system information (including cell size) in text format. Files with the extension .dcd give the trajectory of the atomic coorinates over time (and also include system cell information). Due to storage limitations, large DCD files have been omitted or replaced with new DCD files having the prefix stride50_ including only every 50 frames. The time between frames in these files is 50 * 50000 steps/frame * 4 fs/step = 10 ns. The system cell trajectory is also included for the NPT runs are output/eq_*.xst.Scripts

Files with the .sh extension can be found throughout. These usually provide the highest level control for submission of simulations and analysis. Look to these as a guide to what is happening. If there are scripts with step1_*.sh and step2_*.sh, they are intended to be run in order, with step1_*.sh first.
CONTENTS
========The directory contents are as follows. The directories Sim_Figure1 and Sim_Figure8 include README.txt files that describe the files and naming conventions used throughout this data set.
Sim_Figure1: Simulations of Nacetylated Camidated amino acids (AcXNHMe) at the graphite–water interface.
Sim_Figure2: Simulations of different peptide designs (including acyclic, disulfide cyclized, and NtoC cyclized) at the graphite–water interface.
Sim_Figure3: MMGBSA calculations of different peptide sequences for a folded conformation and 5 misfolded/unfolded conformations.
Sim_Figure4: Simulation of four peptide molecules with the sequence cyc(GTGSGTGGPGGGCGTGTGSGPG) at the graphite–water interface at 370 K.
Sim_Figure5: Simulation of four peptide molecules with the sequence cyc(GTGSGTGGPGGGCGTGTGSGPG) at the graphite–water interface at 295 K.
Sim_Figure5_replica: Temperature replica exchange molecular dynamics simulations for the peptide cyc(GTGSGTGGPGGGCGTGTGSGPG) with 20 replicas for temperatures from 295 to 454 K.
Sim_Figure6: Simulation of the peptide molecule cyc(GTGSGTGGPGGGCGTGTGSGPG) in free solution (no graphite).
Sim_Figure7: Free energy calculations for folding, adsorption, and pairing for the peptide CHP1404 (sequence: cyc(GTGSGTGGPGGGCGTGTGSGPG)). For folding, we calculate the PMF as function of RMSD by replicaexchange umbrella sampling (in the subdirectory Folding_CHP1404_Graphene/). We make the same calculation in solution, which required 3 seperate replicaexchange umbrella sampling calculations (in the subdirectory Folding_CHP1404_Solution/). Both PMF of RMSD calculations for the scrambled peptide are in Folding_scram1404/. For adsorption, calculation of the PMF for the orientational restraints and the calculation of the PMF along z (the distance between the graphene sheet and the center of mass of the peptide) are in Adsorption_CHP1404/ and Adsorption_scram1404/. The actual calculation of the free energy is done by a shell script ("doRestraintEnergyError.sh") in the 1_free_energy/ subsubdirectory. Processing of the PMFs must be done first in the 0_pmf/ subsubdirectory. Finally, files for free energy calculations of pair formation for CHP1404 are found in the Pair/ subdirectory.
Sim_Figure8: Simulation of four peptide molecules with the sequence cyc(GTGSGTGGPGGGCGTGTGSGPG) where the peptides are far above the graphene–water interface in the initial configuration.
Sim_Figure9: Two replicates of a simulation of nine peptide molecules with the sequence cyc(GTGSGTGGPGGGCGTGTGSGPG) at the graphite–water interface at 370 K.
Sim_Figure9_scrambled: Two replicates of a simulation of nine peptide molecules with the control sequence cyc(GGTPTTGGGGGGSGGPSGTGGC) at the graphite–water interface at 370 K.
Sim_Figure10: Adaptive biasing for calculation of the free energy of the folded peptide as a function of the angle between its long axis and the zigzag directions of the underlying graphene sheet.

Meier and Zupan proved that an orientable surface [Formula: see text] in [Formula: see text] admits a triplane diagram with zero crossings if and only if [Formula: see text] is unknotted, so that the crossing number of [Formula: see text] is zero. We determine the minimal crossing numbers of nonorientable unknotted surfaces in [Formula: see text], proving that [Formula: see text], where [Formula: see text] denotes the connected sum of [Formula: see text] unknotted projective planes with normal Euler number [Formula: see text] and [Formula: see text] unknotted projective planes with normal Euler number [Formula: see text]. In addition, we convert Yoshikawa’s table of knotted surface chdiagrams to triplane diagrams, finding the minimal bridge number for each surface in the table and providing upper bounds for the crossing numbers.more » « less

null (Ed.)Let [Formula: see text] be a group acting properly and by isometries on a metric space [Formula: see text]; it follows that the quotient or orbit space [Formula: see text] is also a metric space. We study the Vietoris–Rips and Čech complexes of [Formula: see text]. Whereas (co)homology theories for metric spaces let the scale parameter of a Vietoris–Rips or Čech complex go to zero, and whereas geometric group theory requires the scale parameter to be sufficiently large, we instead consider intermediate scale parameters (neither tending to zero nor to infinity). As a particular case, we study the Vietoris–Rips and Čech thickenings of projective spaces at the first scale parameter where the homotopy type changes.more » « less