Source author record

Paul S. Wenger

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computer Vision Discrete Mathematics Neural and Evolutionary Computing

Catalog footprint

Research overview

11works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Multiple-View Spectral Clustering for Group-wise Functional Community Detection

Functional connectivity analysis yields powerful insights into our understanding of the human brain. Group-wise functional community detection aims to partition the brain into clusters, or communities, in which functional activity is inter-regionally correlated in a common manner across a group of subjects. In this article, we show how to use multiple-view spectral clustering to perform group-wise functional community detection. In a series of experiments on 291 subjects from the Human Connectome Project, we compare three versions of multiple-view spectral clustering: MVSC (uniform weights), MVSCW (weights based on subject-specific embedding quality), and AASC (weights optimized along with the embedding) with the competing technique of Joint Diagonalization of Laplacians (JDL). Results show that multiple-view spectral clustering not only yields group-wise functional communities that are more consistent than JDL when using randomly selected subsets of individual brains, but it is several orders of magnitude faster than JDL.

preprint2016arXiv

Planar digraphs without large acyclic sets

Given a directed graph, an acyclic set is a set of vertices inducing a subgraph with no directed cycle. In this note we show that there exist oriented planar graphs of order $n$ for which the size of the maximum acyclic set is at most $\lceil \frac{n+1}{2} \rceil$ , for any $n$ . This disproves a conjecture of Harutyunyan and shows that a question of Albertson is best possible.

preprint2016arXiv

Unit Hypercube Visibility Numbers of Trees

A visibility representation of a graph $G$ is an assignment of the vertices of $G$ to geometric objects such that vertices are adjacent if and only if their corresponding objects are "visible" each other, that is, there is an uninterrupted channel, usually axis-aligned, between them. Depending on the objects and definition of visibility used, not all graphs are visibility graphs. In such situations, one may be able to obtain a visibility representation of a graph $G$ by allowing vertices to be assigned to more than one object. The {\it visibility number} of a graph $G$ is the minimum $t$ such that $G$ has a representation in which each vertex is assigned to at most $t$ objects. In this paper, we explore visibility numbers of trees when the vertices are assigned to unit hypercubes in $\mathbb{R}^n$ . We use two different models of visibility: when lines of sight can be parallel to any standard basis vector of $\mathbb{R}^n$ , and when lines of sight are only parallel to the $n$ th standard basis vector in $\mathbb{R}^n$ . We establish relationships between these visibility models and their connection to trees with certain cubicity values.

preprint2015arXiv

On the Sum Neccesary to Ensure that a Degree Sequence is Potentially H-Graphic

A sequence of nonnegative integers π=(d_1,d_2,...,d_n) is graphic if there is a (simple) graph G with degree sequence π. In this case, G is said to realize or be a realization of π. Degree sequence results in the literature generally fall into two classes: forcible problems, in which all realizations of a graphic sequence must have a given property, and potential problems, in which at least one realization of πmust have the given property. Given a graph H, a graphic sequence πis potentially H-graphic if there is some realization of πthat contains H as a subgraph. In 1991, Erdős, Jacobson and Lehel posed the following question: Determine the minimum integer σ(H,n) such that every n-term graphic sequence with sum at least σ(H,n) is potentially H-graphic. As the sum of the terms of πis twice the number of edges in any realization of π, the Erdős-Jacobson-Lehel problem can be viewed as a potential degree sequence relaxation of the (forcible) Turán problem, wherein one wishes to determine the maximum number of edges in a graph that contains no copy of H. While the exact value of σ(H,n) has been determined for a number of specific classes of graphs (including cliques, cycles, complete bigraphs and others), very little is known about the parameter for arbitrary H. In this paper, we determine σ(H,n) asymptotically for all H, thereby providing an Erdős-Stone-Simonovits-type theorem for the Erdős-Jacobson-Lehel problem.

preprint2015arXiv

The List Distinguishing Number Equals the Distinguishing Number for Interval Graphs

A \textit{distinguishing coloring} of a graph $G$ is a coloring of the vertices so that every nontrivial automorphism of $G$ maps some vertex to a vertex with a different color. The \textit{distinguishing number} of $G$ is the minimum $k$ such that $G$ has a distinguishing coloring where each vertex is assigned a color from $\{1,\ldots,k\}$ . A \textit{list assignment} to $G$ is an assignment $L=\{L(v)\}_{v\in V(G)}$ of lists of colors to the vertices of $G$ . A \textit{distinguishing $L$ -coloring} of $G$ is a distinguishing coloring of $G$ where the color of each vertex $v$ comes from $L(v)$ . The {\it list distinguishing number} of $G$ is the minimum $k$ such that every list assignment to $G$ in which $|L(v)|=k$ for all $v\in V(G)$ yields a distinguishing $L$ -coloring of $G$ . We prove that if $G$ is an interval graph, then its distinguishing number and list distinguishing number are equal.

preprint2015arXiv

The Unit Bar Visibility Number of a Graph

A \textit{ $t$ -unit-bar representation} of a graph $G$ is an assignment of sets of at most $t$ horizontal unit-length segments in the plane to the vertices of $G$ so that (1) all of the segments are pairwise nonintersecting, and (2) two vertices $x$ and $y$ are adjacent if and only if there is a vertical channel of positive width connecting a segment assigned to $x$ and a segment assigned to $y$ that intersects no other segment. The \textit{unit bar visibility number} of a graph $G$ , denoted $ub(G)$ , is the minimum $t$ such that $G$ has a $t$ -unit-bar visibility representation. Our results include a linear time algorithm that determines $ub(T)$ when $T$ is a tree, bounds on $ub(K_{m,n})$ that determine $ub(K_{m,n})$ asymptotically when $n$ and $m$ are asymptotically equal, and bounds on $ub(K_n)$ that determine $ub(K_n)$ exactly when $n\equiv 1,2\pmod 6$ .

preprint2015arXiv

Uniquely cycle-saturated graphs

Given a graph $F$ , a graph $G$ is {\it uniquely $F$ -saturated} if $F$ is not a subgraph of $G$ and adding any edge of the complement to $G$ completes exactly one copy of $F$ . In this paper we study uniquely $C_t$ -saturated graphs. We prove the following: (1) a graph is uniquely $C_5$ -saturated if and only if it is a friendship graph. (2) There are no uniquely $C_6$ -saturated graphs or uniquely $C_7$ -saturated graphs. (3) For $t\ge6$ , there are only finitely many uniquely $C_t$ -saturated graphs (we conjecture that in fact there are none).

preprint2014arXiv

Extending Precolorings to Distinguish Group Actions

Given a group $Γ$ acting on a set $X$ , a $k$ -coloring $ϕ:X\to\{1,\dots,k\}$ of $X$ is distinguishing with respect to $Γ$ if the only $γ\in Γ$ that fixes $ϕ$ is the identity action. The distinguishing number of the action $Γ$ , denoted $D_Γ(X)$ , is then the smallest positive integer $k$ such that there is a distinguishing $k$ -coloring of $X$ with respect to $Γ$ . This notion has been studied in a number of settings, but by far the largest body of work has been concerned with finding the distinguishing number of the action of the automorphism group of a graph $G$ upon its vertex set, which is referred to as the distinguishing number of $G$ . The distinguishing number of a group action is a measure of how difficult it is to "break" all of the permutations arising from that action. In this paper, we aim to further differentiate the resilience of group actions with the same distinguishing number. In particular, we introduce a precoloring extension framework to address this issue. A set $S \subseteq X$ is a fixing set for $Γ$ if for every non-identity element $γ\in Γ$ there is an element $s \in S$ such that $γ(s) \neq s$ . The distinguishing extension number $\operatorname{ext}_D(X,Γ;k)$ is the minimum number $m$ such that for all fixing sets $W \subseteq X$ with $|W| \geq m$ , every $k$ -coloring $c : X \setminus W \to [k]$ can be extended to a $k$ -coloring that distinguishes $X$ . In this paper, we prove that $\operatorname{ext}_D(\mathbb{R},\operatorname{Aut}(\mathbb{R}),2) =4$ , where $\operatorname{Aut}(\mathbb{R})$ is comprised of compositions of translations and reflections. We also consider the distinguishing extension number of the circle and (finite) cycles, obtaining several exact results and bounds.

preprint2014arXiv

Graph Saturation in Multipartite Graphs

Let $G$ be a fixed graph and let ${\mathcal F}$ be a family of graphs. A subgraph $J$ of $G$ is ${\mathcal F}$ -saturated if no member of ${\mathcal F}$ is a subgraph of $J$ , but for any edge $e$ in $E(G)-E(J)$ , some element of ${\mathcal F}$ is a subgraph of $J+e$ . We let $\text{ex}({\mathcal F},G)$ and $\text{sat}({\mathcal F},G)$ denote the maximum and minimum size of an ${\mathcal F}$ -saturated subgraph of $G$ , respectively. If no element of ${\mathcal F}$ is a subgraph of $G$ , then $\text{sat}({\mathcal F},G) = \text{ex}({\mathcal F}, G) = |E(G)|$ . In this paper, for $k\ge 3$ and $n\ge 100$ we determine $\text{sat}(K_3,K_k^n)$ , where $K_k^n$ is the complete balanced $k$ -partite graph with partite sets of size $n$ . We also give several families of constructions of $K_t$ -saturated subgraphs of $K_k^n$ for $t\ge 4$ . Our results and constructions provide an informative contrast to recent results on the edge-density version of $\text{ex}(K_t,K_k^n)$ from [A. Bondy, J. Shen, S. Thomassé, and C. Thomassen, Density conditions for triangles in multipartite graphs, Combinatorica 26 (2006), 121--131] and [F. Pfender, Complete subgraphs in multipartite graphs, Combinatorica 32 (2012), no. 4, 483--495].

preprint2011arXiv

List Distinguishing Parameters of Trees

A coloring of the vertices of a graph G is said to be distinguishing} provided no nontrivial automorphism of G preserves all of the vertex colors. The distinguishing number of G, D(G), is the minimum number of colors in a distinguishing coloring of G. The distinguishing chromatic number of G, chi_D(G), is the minimum number of colors in a distinguishing coloring of G that is also a proper coloring. Recently the notion of a distinguishing coloring was extended to that of a list distinguishing coloring. Given an assignment L= {L(v) : v in V(G)} of lists of available colors to the vertices of G, we say that G is (properly) L-distinguishable if there is a (proper) distinguishing coloring f of G such that f(v) is in L(v) for all v. The list distinguishing number of G, D_l(G), is the minimum integer k such that G is L-distinguishable for any list assignment L with |L(v)| = k for all v. Similarly, the list distinguishing chromatic number of G, denoted chi_{D_l}(G) is the minimum integer k such that G is properly L-distinguishable for any list assignment L with |L(v)| = k for all v. In this paper, we study these distinguishing parameters for trees, and in particular extend an enumerative technique of Cheng to show that for any tree T, D_l(T) = D(T), chi_D(T)=chi_{D_l}(T), and chi_D(T) <= D(T) + 1.

preprint2011arXiv

Rainbow Matchings of size δ(G) in Properly Edge-colored Graphs

A {\it rainbow matching} in an edge-colored graph is a matching in which all the edges have distinct colors. Wang asked if there is a function f(δ) such that a properly edge-colored graph G with minimum degree δand order at least f(δ) must have a rainbow matching of size δ. We answer this question in the affirmative; f(δ) = 6.5δsuffices. Furthermore, the proof provides a O(δ(G)|V(G)|^2)-time algorithm that generates such a matching.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Paul S. Wenger

Research overview

Is this your work?

11 publications

Multiple-View Spectral Clustering for Group-wise Functional Community Detection

Planar digraphs without large acyclic sets

Unit Hypercube Visibility Numbers of Trees

On the Sum Neccesary to Ensure that a Degree Sequence is Potentially H-Graphic

The List Distinguishing Number Equals the Distinguishing Number for Interval Graphs

The Unit Bar Visibility Number of a Graph

Uniquely cycle-saturated graphs

Extending Precolorings to Distinguish Group Actions

Graph Saturation in Multipartite Graphs

List Distinguishing Parameters of Trees

Rainbow Matchings of size δ(G) in Properly Edge-colored Graphs

See the researcher in context

Building this map preview