Graph theoretical analysis is a powerful tool for quantitatively evaluating brain connectivity networks. Conventionally, brain connectivity is assumed to be temporally stationary, whereas increasing evidence suggests that functional connectivity exhibits temporal variations during dynamic brain activity. Although a number of methods have been developed to estimate time-dependent brain connectivity, there is a paucity of studies examining the utility of brain dynamics for assessing brain disease states. Therefore, this paper aims to assess brain connectivity dynamics in Parkinson's disease (PD) and determine the utility of such dynamic graph measures as potential components to an imaging biomarker. Resting-state functional magnetic resonance imaging data were collected from 29 healthy controls and 69 PD subjects. Time-varying functional connectivity was first estimated using a sliding windowed sparse inverse covariance matrix. Then, a collection of graph measures, including the Fiedler value, were computed and the dynamics of the graph measures were investigated. The results demonstrated that PD subjects had a lower variability in the Fiedler value, modularity, and global efficiency, indicating both abnormal dynamic global integration and local segregation of brain networks in PD. Autoregressive models fitted to the dynamic graph measures suggested that Fiedler value, characteristic path length, global efficiency, and modularity were all less deterministic in PD. With canonical correlation analysis, the altered dynamics of functional connectivity networks, and particularly dynamic Fiedler value, were shown to be related with disease severity and other clinical variables including age. Similarly, Fiedler value was the most important feature for classification. Collectively, our findings demonstrate altered dynamic graph properties, and in particular the Fiedler value, provide an additional dimension upon which to non-invasively and quantitatively assess PD.