Westudy Properties of Multidomain Proteins from a Graph Theoretical Perspective.In Particular, We Demonstrate Connections BeTween Properties of the Domainoverlap Graph and Certain Variants of Dollo Parsimony Models. We Apply Ourgraph Theoretical Results to AdDress Several Interrelated Questions: Doproteins Acquire New Domains Infrequently, or Often Enough That the Samecombinations of Domains Will Be Created Repeatedly Through Independent Events?Once Domain Architectures Are Created, Do They Persist? In Other Words, Is TheexisTence of Ancestral Proteins With Domain Compositions Not Observed Incontemporary Proteins Unlikely? Our Experimental Results Indicate Thatindependent Merges of Domain Pairs Are Not Uncommon In Large Super- Families.